# Regular Expressions

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 language**L(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.

Contents

## 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

RE_{1} = a(aa)^{*} and RE_{2} = (aa)^{*}

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

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

L_{1} ∪ L_{2} = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,…….}

(Strings of all possible lengths excluding Null)

RE (L_{1} ∪ L_{2}) = 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

RE_{1} = a(a^{*}) and RE_{2} = (aa)^{*}

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

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

L_{1} ∩ L_{2} = { aa, aaaa, aaaaaa,…….} (Strings of even length excluding Null)

RE (L_{1} ∩ L_{2}) = 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 −

RE_{1} = a (a^{*}) and RE_{2} = (aa)^{*}

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

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

L_{1} – L_{2} = {a, aaa, aaaaa, aaaaaaa, ….}

(Strings of all odd lengths excluding Null)

RE (L_{1} – L_{2}) = a (aa)^{*} which is a regular expression.

**Hence, proved.**

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

**Proof −**

We have to prove **L ^{R}** is also regular if

**L**is a regular set.

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

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

L^{R} = {10, 01, 11, 01}

RE (L^{R})= 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 RE_{1} = (0+1)*0 and RE_{2} = 01(0+1)^{*}

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

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

Then, L_{1} L_{2} = {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.

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^{*}