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:
- Union
- Concatenation
- 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
- Regular expression is language defining notation in terms of algebraic description.
- The languages accepted by finite automata, or regular language, is easily described by simple expressions called regular expressions.
- It is more precise and formal as compared to any natural language.
- In contrast to the transition graph, regular expressions can be conveniently written out in a line from left to right.
- 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