Chapter 3: The Theorv of Automata ~ 95
-----------------"---Note: The transition diagram for the minimum state automaton is described
by Fig. 3.13. The states qo and q.', are identified and treated as one state.
(SO also are ql, q7 and q3' qs) But the transitions in both the diagrams (i.e.
Figs. 3.12 and 3.13) are the same. If there is an arrow from qi to (jj with label
a. then there is an arrow from [q;J to lq;] with the same label in the
diagram for minimum state automaton. Symbolically, if O(qi' a) = 'ii' then
8'([q;], a) = [q;J.
1
I---~o-_ _A
7 [q2]
o
o
! ' \
Fig. 3.13 Minimum state automaton of Example 3,13,
EXAMPLE 3.14
Construct the minimum state automaton equivalent to the transition diagram
given by Fig. 3.14.
b
a
-G- b 0- ' ~
! '~
I~
b
t\
I
\
I
\
I
I
I '
\
a I \
'I :'
I' b
I r
\;1
,
I
~
\ ,
~
~
\~
0--\:~)
~--(i))b
b
Fig. 3.14 Finite automaton of Example 3,14,
Solution
We construct the transition table as given by Table ,3.23.