Theoretical computer science for Internal Exam (TYBCS) (SEM 5)

 Chapter 1: Finite Automaton

Chapter 2: Regular Expressions

1. Literals: Characters that match themselves. For example, the regular expression a matches the character 'a'.

2. Concatenation: Concatenation of characters or sub-expressions. For example, abc matches the string 'abc'.

3. Alternation (|): The pipe symbol '|' represents alternation and is used to specify alternatives. For example, a|b matches either 'a' or 'b'.

4. Kleene Star (*): The asterisk '*' denotes zero or more occurrences of the preceding element. For example, a* matches zero or more 'a' characters.

5. Kleene Plus (+): The plus symbol '+' denotes one or more occurrences of the preceding element. For example, a+ matches one or more 'a' characters.

6. Grouping ( ): Parentheses are used to group sub-expressions. For example, (ab|cd)* matches zero or more repetitions of 'ab' or 'cd'.

7. Character Classes [ ]: Square brackets are used to define a character class, which matches any single character from the set. For example, [aeiou] matches any vowel.

8. Ranges (-): Inside character classes, you can use a hyphen '-' to specify a range of characters. For example, [0-9] matches any digit.

9. Wildcard (.): The dot '.' matches any single character except a newline.

10. Escape (): The backslash '' is used to escape special characters, allowing you to match them literally. For example, \. matches a period '.'

11. Anchors (^ and $): The caret '^' represents the start of a line, and the dollar sign '$' represents the end of a line. For example, ^abc$ matches the entire string 'abc'.

12. Quantifiers (?, {n}, {n,}, {n,m}): Quantifiers specify the exact number of occurrences. For example, a{3} matches exactly three 'a' characters, and b{2,4} matches between two and four 'b' characters.

Q. Regular Expressions - Definition & Examples.

Answer: 

Normal Definition: The language accepted by finite automata are described or represented by simple expressions called Regular Expressions. It is a sequence of characters that defines a search pattern. It is used for matching strings with a set of strings.They are also called as rational expressions. 

Formal Definition: 2.1.1 

Examples: 2.1.2

Q.