Home »
Theory of Computation
Regular Expressions in Theory of Computation
Here, we are going to learn about the Regular expression in Theory of computation – its definition, examples and identities.
Submitted by Mahak Jain, on November 14, 2018
Definition of regular expression:
- ε also represents a Regular Expression which means the language contains a string that is empty. (L (ε) = {ε})
- φ denotes an empty language and also represents a regular expression. (L (φ) = {})
- If a denotes a Regular Expression Then Language L = {a}
-
If A is a Regular Expression represents the language L(A) and B is a Regular Expression represents the language L(B), then
- A + B is a Regular Expression represents the language L(A) ∪ L(B) where L(A+B) = L(A) ∪ L(B).
- A.B is a Regular Expression represents the language L(A). L(B) where L (A.B) = L(A). L(B)
- RE* is a Regular Expression representing the language L(RE*) where L(RE*) = (L(RE)) *
Examples:
| Regular Expressions |
Set |
| (a + 1a*) |
L = { a, 1, 1a, 1aa, 1aaa, 1aaaa, … } |
| (a*1a*) |
L = {1, a1, 1a, a1a, aa1a, …} |
| (a + ε)(1 + ε) |
L = {ε, a, 1, a1} |
| (0+b)* |
Set of strings of 0’s and b’s of any length including the null string. So L = { ε, 0, b, 00, 0b , bb , b0, 000…….} |
| (0+b)*0bb |
Set of strings of 0’s and b’s ending with the string 0bb. So L = {0bb, 00bb, b0bb, 000bb, 0b0bb, …………..} |
| (aa)* |
Set consisting of even number of a’s including empty string, So L= {ε, aa, aaaa, aaaaaa, ……….} |
| (00)*(bb)*b |
Set of strings consisting of even number of 0’s followed by odd number of b’s , so L = {b, 00b, 00bbb, 00bbbbb, 0000b, 0000bbb, …………..} |
| (00 + 0b + b0 + bb)* |
String of 0’s and b’s of even length can be obtained by concatenating any combination of the strings 00, 0b, b0 and bb including null, so L = {00, 0b, b0, bb, 000b, 00b0, ………….} |
Identities followed by Regular Expressions:
If A, B, C, D represents regular expressions
- ∅* = ε
- ε* = ε
- AA* = A*A
- A*A* = A*
- (A*) * = A*
- AA* = A*A
- (AB)*A =A(BA)*
- (a+d)* = (a*d*)* = (a*+d*)*
- C + ∅ = ∅ + C = C
- A ε = ε A = A
- ∅B = B∅ = ∅
- A + A = A
- L (A+ B) = LA + LB
- (A + B) L = AL BL
- ε + AA* = ε + A*A = A*