Regular Expressions (Regex): A regular expression is a sequence of characters that defines a search pattern. It is commonly used for string matching within a text.
Example
The regular expression (a + b * c)* describes the language of all strings over the alphabet {a, b, c} where any combination of a, b, and c is allowed, including the empty string.
Operations on Regular Expressions
Concatenation (r1 r2): Combines two regular expressions.
Union (r1 + r2): Represents alternatives between two regular expressions.
Kleene Star (r*): Denotes zero or more repetitions of the preceding regular expression.
2. Recursive Definition
Primitive Regular Expressions
Empty Set (∅): Represents the language containing no strings.
Empty String (λ): Represents the language containing only the empty string.
Atomic Symbol (α): Represents a single character from the alphabet.
Operations
Union (r1 + r2): Represents the union of two languages.
Concatenation (r1 r2): Represents the concatenation of two languages.
Kleene Star (r*): Represents zero or more repetitions of a language.
3. Examples
Example 1
Regular Expression: (a + b) * a*
Language: All strings with any combination of a and b, followed by zero or more a.
Example 2
Regular Expression: (a + b*) * (c + ∅)
Language: All strings with any combination of a and zero or more b, followed by either c or the empty string.
4. Languages of Regular Expressions
Definition
For a regular expression r, the language L(r) is the set of all strings that can be generated by r.
Example
For the regular expression (a + b * c)*, L((a + b * c)*) is the set of all strings over {a, b, c}.
5. Conversion from Finite Automaton (FA) to Regular Expression
Generalized Transition Graph
Represents the transitions of a finite automaton.
The final regular expression is obtained by combining the regular expressions associated with the transitions.
Example
Transition graph with states q0, q1, q2, q3, q4, and transitions labeled with regular expressions.
The final regular expression r is obtained by combining the expressions associated with transitions.
