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. 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*