Theory Of Computation

Section B

Regular Expression

A Regular Expression can be recursively defined as follows:

1. ε is a Regular Expression indicates the language containing an empty string. (L (ε)

= {ε})

2. φ is a Regular Expression denoting an empty language. (L (φ) = { })

3. x is a Regular Expression where L={x}

4. If X is a Regular Expression denoting the language L(X) and Y is a Regular

Expression denoting the language L(Y), then

(a) X + Y is a Regular Expression corresponding to the language L(X) U L(Y)

where L(X+Y) = L(X) U L(Y).

(b) X . Y is a Regular Expression corresponding to the language L(X) . L(Y)

where L(X.Y)= L(X) . L(Y)

(c) R* is a Regular Expression corresponding to the language L(R*) where

L(R*) = (L(R))*

5. If we apply any of the rules several times from 1 to 5, they are Regular Expressions.

Some RE Examples