Regular Expressions

Posted By on April 29, 2016


Download PDF
Recurrence Relation
Finite Automaton

A Regular Expression can be recursively defined as follows −

  • ε is a Regular Expression indicates the language containing an empty string. (L (ε) = {ε})
  • φ is a Regular Expression denoting an empty language. (L (φ) = { })
  • x is a Regular Expression where L={x}
  • If X is a Regular Expression denoting the language L(X)and Y is a Regular Expression denoting the languageL(Y), then
    • X + Y is a Regular Expression corresponding to the language L(X) ∪ L(Y) where L(X + Y) = L(X) ∪ L(Y).
    • X . Y is a Regular Expression corresponding to the language L(X) . L(Y) where L(X.Y)= L(X) . L(Y)
    • R* is a Regular Expression corresponding to the language L(R*) where L(R*) = (L(R))*
  • If we apply any of the rules several times from 1 to 5, they are Regular Expressions.

Some RE Examples

Regular Expressions Regular Set
(0 + 10*) L= { 0, 1, 10, 100, 1000, 10000, … }
(0*10*) L={1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L= {ε, 0, 1, 01}
(a + b)* Set of strings of a’s and b’s of any length including the null string. So L= { ε, 0, 1,00,01,10,11,…….}
(a + b)*abb Set of strings of a’s and b’s ending with the string abb, So L = {abb, aabb, babb, aaabb, ababb, …………..}
(11)* Set consisting of even number of 1’s including empty string, So L= {ε, 11, 1111, 111111, ……….}
(aa)*(bb)*b Set of strings consisting of even number of a’s followed by odd number of b’s , so L= {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, …………..}
(aa + ab + ba + bb)* String of a’s and b’s of even length can be obtained by concatenating any combination of the strings aa, ab, ba and bb including null, so L= {aa, ab, ba, bb, aaab, aaba, …………..}

Regular Sets

Any set that represents the value of the Regular Expression is called a Regular Set.

Properties of Regular Sets

Property 1 The union of two regular set is regular.

Proof

Let us take two regular expressions

RE1 = a(aa)* and RE2 = (aa)*

So, L1= {a, aaa, aaaaa,…..} (Strings of odd length excluding Null)

and L2={ ε, aa, aaaa, aaaaaa,…….} (Strings of even length including Null)

L1 ∪ L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,…….}

(Strings of all possible lengths excluding Null)

RE (L1 ∪ L2) = a* (which is a regular expression itself)

Hence, proved.

Property 2. The intersection of two regular set is regular.

Proof −

Let us take two regular expressions

RE1 = a(a*) and RE2 = (aa)*

So, L1 = { a, aa, aaa, aaaa, ….} (Strings of all possible lengths excluding Null)

L2 ={ ε, aa, aaaa, aaaaaa,…….} (Strings of even length including Null)

L1 ∩ L2 = { aa, aaaa, aaaaaa,…….} (Strings of even length excluding Null)

RE (L1 ∩ L2) = aa(aa)* which is a regular expression itself.

Hence, proved.

Property 3. The complement of a regular set is regular.

Proof −

Let us take a regular expression −

RE = (aa)*

So, L = {ε, aa, aaaa, aaaaaa, …….} (Strings of even length including Null),

Complement of L is all the strings that is not in L.

So, L’ = {a, aaa, aaaaa, …..} (Strings of odd length excluding Null)

RE (L’) = a(aa)* which is a regular expression itself.

Hence, proved.

Property 4. The difference of two regular set is regular.

Proof −

Let us take two regular expressions −

RE1 = a (a*) and RE2 = (aa)*

So, L1= {a, aa, aaa, aaaa, ….} (Strings of all possible lengths excluding Null)

L2 = { ε, aa, aaaa, aaaaaa,…….} (Strings of even length including Null)

L1 – L2 = {a, aaa, aaaaa, aaaaaaa, ….}

(Strings of all odd lengths excluding Null)

RE (L1 – L2) = a (aa)* which is a regular expression.

Hence, proved.

Property 5. The reversal of a regular set is regular.

Proof −

We have to prove LR is also regular if L is a regular set.

Let, L= {01, 10, 11, 10}

RE (L)= 01 + 10 + 11 + 10

LR = {10, 01, 11, 01}

RE (LR)= 01 + 10 + 11 +10 which is regular

Hence, proved.

Property 6. The closure of a regular set is regular.

Proof −

If L = {a, aaa, aaaaa, …….} (Strings of odd length excluding Null)

i.e., RE (L) = a (aa)*

L*= {a, aa, aaa, aaaa , aaaaa,……………} (Strings of all lengths excluding Null)

RE (L*) = a (a)*

Hence, proved.

Property 7. The concatenation of two regular sets is regular.

Proof −

Let RE1 = (0+1)*0 and RE2 = 01(0+1)*

Here, L1 = {0, 00, 10, 000, 010, ……} (Set of strings ending in 0)

and L2 = {01, 010,011,…..} (Set of strings beginning with 01)

Then, L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,………….}

Set of strings containing 001 as a substring which can be represented by an RE: (0 + 1)*001(0 + 1)*

Hence, proved.

Identities Related to Regular Expressions

Given R, P, L, Q as regular expressions, the following identities hold −

  • * = ε
  • ε* = ε
  • R+ = RR* = R*R
  • R*R* = R*
  • (R*)* = R*
  • RR* = R*R
  • (PQ)*P =P(QP)*
  • (a + b)* = (a*b*)* = (a* + b*)* = (a + b*)* = a*(ba*)*
  • R + ∅ = ∅ + R = R (The identity for union)
  • R ε = ε R = R (The identity for concatenation)
  • ∅ L = L ∅ = ∅ (The annihilator for concatenation)
  • R + R = R (Idempotent law)
  • L (M + N) = LM + LN (Left distributive law)
  • (M + N) L = LM + LN (Right distributive law)
  • ε + RR* = ε + R*R = R*

 

Recurrence Relation
Finite Automaton

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com