Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 227

b

a

a b

b

a

a

a

b 4

2

3

8

1

7

5

6

Fig. 9.11

For example, consider a state diagram shown in Fig. 9.11 then,

8 R 67 = {aba, bab}, but aab^ ∉^8 R 67

Expression iRjK can be obtained by using methods of induction i.e.,

Initially there is no intermediate state between qi to qj, so k = 0.

(For k = 0)

l iRj^0 = {al ∈ Σ / δ(qi, al) = qj} if, i ≠ j and state is connected by single arc†.

l If, i = j then,

iRi^0 = {al^ ∈^ Σ / δ(qi, al) = qi} ∪ {∈}.‡

l If there is no symbol between qi and qj then,

iRj

(^0) = ΦΦΦΦΦ i.e., δ(q
i, Φ) = Φ, [there is no path between them]
So, for the base cases of regular expression iRjK can be constructed.
Apply induction hypothesis (for general k) and determine the expression iRjK for the path
from state qi to state qj i.e., for all intermediate states qm, where ∀qm < qk and (qi, qj) = qk.
qi qj
£qk–1

qk
£qk–1
£qk–1
O O
qk–1
qk
Fig. 9.12
† If there are m multiple paths from state i → j over symbols a 1 , a 2 , ......, am then, regular
expression will be a 1 + a 2 + ...... am.
‡ If there is no symbol (start state is the final state) then regular expression is ∈∈∈∈∈.
If a 1 , a 2 , ......, am are m multiple symbols i.e. transition on these symbols return back to same
state then regular expression will be a 1 + a 2 + ...... am
aa 12 , , ......,am