ADVERTISEMENT
ADVERTISEMENT

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



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.