Chapter 5: Regular Sets and Regular Grammars Q 141
Step 3 If 1') is an initial state, make V~ also as initial state.
Step 4 If 1'~ is a final state. make Vj also as the final state.
EXAMPLE 5.5
Consider a finite automaton, with A-moves, given in Fig. 5.1. Obtain an
equivalent automaton without A-moves.
o
2
Fig. 5.1 Finite automaton of Example 5.5.
Solution
We first eliminate the A-move fram qo ta q) to get Fig. 5.2(a). qj is made
an initial state. Tnen we eliminate the A-move from qo to q~ in Fig. 5.2(a)
to get Fig. 5.2(b). As q~ is a final state. qo is also made a final state. Finally,
the A-move from q) to q~ is eliminated in Fig. 5.2(c).
0
1
~
-8
A
i
A
(a)
2
A
2
(b)
o
2
2
2
(c)
Fig. 5.2 Transition system for Example 5.5, without A-moves.