Mathematical Foundation of Computer Science

DHARM

232 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Example 9.7. Convert the following DFA to regular expression.

1

4

2

3

1 0

0

1

1

0

0 1

Fig. 9.20
DFA shown in Fig. 9.20 has state 1 is the starting state as well as the final state. So, let
us select the state 4 is eliminated first.
l The regular expression for the incoming arc (from state 2 to 4 on symbol 1) is 1 ,
l The regular expression for an repetitive arc (state 4 to itself on symbol 0) 0 ,
l The regular expression for an outgoing arc (from state 4 to1 on symbol 1) is 1.
Hence, the equivalent regular expression after eliminating the state 4 will be 1.0. 1. So
a new arc shown in Fig. 9.21 will be labeled by this regular expression (let it be r) from state 2
to state 3. Thus, we obtain a now DFA i.e.,

1

2

3

1 0

0

(^01) r=1.0.1
Fig. 9.21
(Now eliminate state 3)
Observe the incoming and the outgoing arcs of state 3, corresponding to them we find
the equivalent regular expressions i.e.,
l The regular expression for the incoming arc from state 2 to 3 which is labeled by r
and then the regular expression for the out going arc from state 3 to 1 on symbol 0 is
0. So, through this path regular expression will be, r. 0.
l The regular expression for the incoming arc from state 2 to 3 labeled by r and then
from the regular expression for the path from state 3 to 2 to 3 on symbol 1 followed by
0, is 1. 0 with possibility of zero/more times repetition of this path hence regular
expression will be (1. 0)and then the regular expression for the outgoing arc from
state 3 to 1 is 0. Hence, through this path regular expression will be r. (1. 0 ) 0
The possibilities of both discussed cases can be equivalently represented by the regular
expression r. (1. 0 ) 0.
l The regular expression for the incoming arc from state 2 to 3 on symbol 0 is 0 and the
regular expression for the outgoing arc from state 3 to 1 on symbol 0 is again 0. So, we
obtain the regular expression 0.0.