DHARMREGULAR EXPRESSIONS 2319.5 Construction of Regular Expression from DFA.............................................................
(By Eliminating States)
From a given DFA a regular expression can be constructed directly through step-by-step
eliminations of states from the state diagram. A state can be eliminated equivalently by the
regular expression which is constructed in the following sequence, i.e.,
l Find the regular expression for all incoming arcs to that state,
l Find the regular expression for all repetition arcs that returns to that state itself, and
l Find the regular expression for all outgoing arcs from that state.
Consider an example of a DFA shown in Fig. 9.17.2 3(^1) 1, 0
1 0
0
1
Fig. 9.17
(Let us eliminate state 2)
Regular expression for the incoming arc (from state 1 on symbol 1) is 1. Regular expres-
sion for the repetition arc (on state 2 itself on symbol 1) is 1 and then the regular expression
for outgoing arc (from state 2 to state 3) is 0. Hence, the transition arc from state 1 to state 3
after eliminating state 2 will be labeled by regular expression 1. 1. 0 which is shown in
Fig. 9.18.
3
1, 0
1
0
1.1.0
Fig. 9.18
(Now eliminate state 1)
State has an repetition arc labeled by symbol 0 so, the regular expression is 0 , followed
by an outgoing arc, which is labeled by regular expression 1. 1. 0. So, elimination of state 1
will result the regular expression 0. (1. 1. 0 ). (Fig. 9.19)
(^3) 1, 0
0.(1.1.0)
Fig. 9.19
Now the incoming arc labeled by the regular expression 0. (1. 1. 0) reaches to state
3, which is the accepting state and regular expression for the repetition arc over symbol 0 or 1
is (1 + 0). Thus we obtain the final regular expression i.e.,
0. (1. 1. 0 ). (1 + 0)*