Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 229

Example 9.6. Construct the regular expression for the DFA shown in Fig. 9.13.

1 1 2

0 1

0

Fig. 9.13

Sol. We construct the regular expression using the theorem 9.2. So for the base case i.e. con-
struct the expression from state 1 to the state j (where j = 1 and 2), and assume that there is no
intermediate state (k = 0) between 1 and j. Hence, expression 1 Rj^0 is computed and shown in
Fig. 9.14.

State Language Regular

Transition Expression

from

1 → 1 1 R 10 Choices in between either no symbol or symbol 0 0 + ∈∈∈∈∈

1 → 2 1 R 20 A single arc labeled by symbol 1 1

2 → 1 2 R 10 A single arc labeled by symbol 0 0

2 → 2 2 R 20 Choice in between either no symbol (∈) or symbol 1 1 + ∈∈∈∈∈

Fig. 9.14

l Now we construct the expression for inductive part (for k = 1), i.e., 1 Rj^1 (for j = 1, 2)

By using the rule iRjK = iRjK–1 + iRkK–1. (kRkK–1)*. kRjK–1.

l 1 R 11 = 1 R 10 + 1 R 10 ( 1 R 10 )* 1 R 10

[Put the value of 1 R 10 from table (for j = 1, j – 1 returns 0 but 0 is no such state so state

remains 1]

= (0 + ∈∈∈∈∈) + (0 + ∈∈∈∈∈)(0 + ∈∈∈∈∈)*(0 + ∈∈∈∈∈) = (0 + ∈∈∈∈∈) + (0 + ∈∈∈∈∈)0*(0 + ∈∈∈∈∈)

= 0 + ∈∈∈∈∈ + 0* = 0*

l 1 R 21 = 1 R 20 + 1 R 10 ( 1 R 10 )* 1 R 20

= 1 + (0 + ∈∈∈∈∈)(0 + ∈∈∈∈∈)*. 1 = 0* 1

l 2 R 11 = 2 R 10 + 2 R 10 ( 1 R 10 )* 1 R 10

= 0 + 0. (0 + ∈)* (0 + ∈) = 0 + 0. 0* = 0. 0*

l 2 R 21 = 2 R 20 + 2 R 10 ( 1 R 10 )* 1 R 20

= (1 + ∈) + 0(0 + ∈)* 1 = (1 + ∈∈∈∈∈) + 0 0* 1

Hence we obtain the expression 1 Rj^1 (for j = 1, 2). Fig. 9.15.