Regular expression

A regular expression is a sequence of patterns that defines a string.

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

Operators of Regular expression

The definition of regular expression includes three basic operators: 

1. Union
2. Concatenation
3. Closure

1. Union: If p and q are regular expressions, then p+q is a regular expression denoting the union of L(p) and L(q), that is, L(p+q) = L(p) U L(q)2.

2. Concatenation: If p and q are regular expressions, then p.q is a regular expression denoting the concatenation of L(p) and L(q), that is, L(pq) = L(p) L(q).

3. Closure: If p is regular expression, then so is p*, denoting the closure of L(p), that is L(p*) = (L(p))*.

Some regular expressions and its language

Regular expression	Language
r=a	L(r) = {a}
r = ab	L(r) = {ab}
r = a+b	L(r) = {a, b}
r = a*	L(r) = {∈, a, aa, aaa, …}
r = ab*	L(r) = {a, ab, abb, abbb,….}
r = (ab)*	L(r) = {∈, ab, abab, ababab, …}
r = a(a+b)	L(r) = {aa, ab}

a* VS a⁺

a* =  a power * means, a may not exist or may exist.

a⁺ = a power + means, a exist atleast once. 

Characterstics of regular expression

1. Regular expression is language defining notation in terms of algebraic description.
2. The languages accepted by finite automata, or regular language, is easily described by simple expressions called regular expressions.
3. It is more precise and formal as compared to any natural language. 
4. In contrast to the transition graph, regular expressions can be conveniently written out in a line from left to right.
5. Main two areas of application of regular expression are:
   • Lexical analysis (compilers) and
   • text editors.

---

Regular Expression examples:

Example 1: Let Σ = {a, b}. Write regular expression to define language consisting of strings w such that, w contains only a’s or only b’s of length zero or more.

Solution:  r = a* + b*

---

Example 2: Let Σ = {a, b}. Write regular expression to define language consisting of strings w such that, w is of length one or more and contains only a’s or only b’s. r = a+ + b+

Solution:  r = a⁺+ b⁺

---

Example 3: Let Σ = {a, b}. Write regular expression to define language consisting of strings w such that, w contains zero or more a’s followed by zero or more b’s

Solution: r = a*b*

---

Example 4: Let Σ = {a, b}. Write regular expression to define language consisting of strings w such that, w of length even 

Solution: r = [(a + b) (a + b)]*

More Example