What is Regular Expression

RGPV PYQs

Q. What is a regular expression?

Solution. The language accepted by finite automata can be easily described by simple expressions called regular expressions.

Let,
Σ denotes the input set.

1. Φ is a regular expression that denotes the empty set.
2. ε is a regular expression and denotes the set {ε}, and it is a null string.
3. For each ‘a’ in Σ, ‘a’ is a regular expression and denotes the set (a).
4. If R1 and R2 are regular expressions denoting the Languages L1 and L2, respectively, then
   • R1+R2 is equivalent to LI ∪ L2, i.e., union.
   • R1R2 is equivalent to L1 ∩ L2, i.e. concatenation
   • R* is equivalent to L1*, i.e., closure.

The R* is known as kleen closure or closure, which indicates the occurrence of R an infinite number of times.

Some other examples of regular expressions are:

1. R = a, i.e., all combinations of a.
2. R = a+, i.e., all combinations of a without a null string.
3. R = (a+b), i.e., strings contain any number of a and b