Mathematical Foundation of Computer Science

DHARM

230 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

State Language Regular

Transition Expression

from

1 → 1 1 R 11 Choice in between either no symbol or finite 0*

number of 0’s

1 → 2 1 R 21 A single arc labeled by symbol 1 or Finite number 0* 1

of 0’s followed by 1

2 → 1 2 R 11 A single arc labeled by symbol 0 or followed by 0. 0*

one/more transition/s on 0’s

2 → 2 2 R 21 Choice in between either symbol 1 or no symbol or 1 + ∈∈∈∈∈ + 0 0*1

through state 1

Fig. 9.15

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

l 1 R 12 = 1 R 11 + 1 R 21 ( 2 R 21 )* 2 R 11

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

l 1 R 22 = 1 R 21 + 1 R 21 ( 2 R 21 )* 2 R 21

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

= 0* 1 [1 + ∈∈∈∈∈ + 0 0 *1] *

l 2 R 12 = 2 R 11 + 2 R 21 ( 2 R 21 )* 2 R 11

= 0. 0* + [1 + ∈∈∈∈∈ + 0 0*1] [1 + ∈∈∈∈∈ + 0 0*1 ]*. 0 0*

= [1 + ∈∈∈∈∈ + 0 0*1 ]*. 0 0*

l 2 R 22 = 2 R 21 + 2 R 21 ( 2 R 21 )* 2 R 21

= [1 + ∈∈∈∈∈ + 0 0*1 ]+

Hence the table for expression 1 Rj^2 (for j = 1, 2) is shown in Fig. 9.16.

State Transition Language Regular Expression

from

1 → 1 1 R 12 0* + 0* 1 (1 + ∈ + 0 0*1 )* 0 0*

1 → 2 1 R 22 0* 1 [1 + ∈∈∈∈∈ + 0 0 *1] *

2 → 1 2 R 12 [1 + ∈∈∈∈∈ + 0 0*1 ]*. 0 0*

2 → 2 2 R 22 [1 + ∈∈∈∈∈ + 0 0*1 ]+

Fig. 9.16
Now the final regular expression for the DFA shown in Fig. 9.13 will be constructed by
taking the unions of all the expression whose state 1 is the starting state and state 2 is the
final state, i.e. 1 R 22.
Where, 1 R 22 = 0 1 [1 + ∈ + 0 0 1]
Therefore the regular expression is 01 [1 + ∈∈∈∈∈ + 001].