Regular expression

A regular expression is a sequence of pattern 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. 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 expressionLanguage
r=aL(r) = {a}
r = abL(r) = {ab}
r = a+bL(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, regular language, is easily described by simple

3. expressions called as regular expression

4. It is more precise and formal as compared to any natural language. 

5. In contrast to the transition graph, regular expressions can be conveniently written out in a line from left to right.

6. Main two areas of application of regular expression are: Lexical analysis (compilers) and text editors.