156 ~ Theory of Computer Science
EXAMPLE 5.14
Constmct a DFA with reduced states equivalent to the r.e. 10 + (0 + 11»)0*1.
Solutioh
Step 1 (Construction of NDFA) The l' operation +. concatenation and *. and the A-moves in successive steps. The
step-by-step constmction is given in Figs. 5.21(a)-5.21(e).
-6)f-----:. 1 ;;:..o_+.;.:(0,--(:_)1:-:1,L)0;;:..*.;..1_ _~.0
10
(0 + 11)0*1
(b) Eiimination of +,
o
(c\ Elimination of concatenation and *
'~q
r
c
---+1~
o
(d) Elimination of +,
o
o
0
\
( \
1\
~
\
/'*
GJ'
(e) Elimination of .\-moves.
Fig. 5.21 Construction of finite automaton for Example 5.14,