Chapter 3: The Theory of Automata );;I, 81
When Ixl = O. o(qo, A) = {qoL and by definition of o~ [/(q6. A) =
qa =[qol So. (3.5) is true for x with Ix i ::: O. Thus there is basis for induction.
Assume that (3.5) is true for all strings y with Iy I S; m. Let x be a
string of length In + 1. We can write x as va, where 'y' = 111 and a E L. Let
o(qo, 1') = {p, ..., Pi} and o(qo. ya) = {rl' r2' .... rd· As Iyi S; In, by
Induction hypothesis we have
O'(qo· y) = [PI, .... p;]
(3.6)
Also.
{rl' r~ .... r;} = O(qo, ya) = O(o(qo, Y). a) ::: O({PI, .... Pj}, a)
By definition of o~
(3.7)
Hence.
O'(q(;. yay = o/(o/(q'o. y), a) = O'([PI . ... , Pi], a)
by (3.6)
::: [rl' .... rd
by (3.7)
Thus we have proved (3.5) for x = .va.
By induction. (3.5) is true for all strings x. The other part (i.e. the 'only if'
part), can be proved similarly, and so (3.4) is established.
Now. x E T(M) if and only if O(q. x) contains a state of F. By (3.4).
8(qo, x) contains a state of F if and only if 8'(qo, x) is in F'. Hence. x E T(M)
if and only if x E T(Af'). This proves that DFA M' accepts L. I
Vote: In the construction of a deterministic finite automaton M 1 equivalent to
a given nondetelministic automaton M, the only difficult part is the construction
of 8/ for M j • By definition.
k
8'([q1 ... qd, a) = U 8(q;, a)
l=l
So we have to apply 8 to (q;. a) for each i = 1. 2..... k and take their
union to get o'([q] .. , qd. a).
When 8 for /1'1 is given in telms of a state table. the construction is simpler.
8(q;, a) is given by the row corresponding to q; and the column corresponding
to a. To construct 8'([ql ... qk]. a), consider the states appearing in the rows
corresponding to qj
, ql;o and the column corresponding to a. These states
constitute 8'([q]
qd. a).
Note: We write 8' as 8 itself when there is no ambiguity. We also mark the
initial state with ~ and the final state with a circle in the state table.
EXAMPLE 3.6
Construct a deterministic automaton equivalent to
M ::: ({qo. qd· {O. l}. 8, qo, {qoD
where 8 is defined by its state table (see Table 3.2).
When Ixl = O. o(qo, A) = {qoL and by definition of o~ [/(q6. A) =
qa =[qol So. (3.5) is true for x with Ix i ::: O. Thus there is basis for induction.
Assume that (3.5) is true for all strings y with Iy I S; m. Let x be a
string of length In + 1. We can write x as va, where 'y' = 111 and a E L. Let
o(qo, 1') = {p, ..., Pi} and o(qo. ya) = {rl' r2' .... rd· As Iyi S; In, by
Induction hypothesis we have
O'(qo· y) = [PI, .... p;]
(3.6)
Also.
{rl' r~ .... r;} = O(qo, ya) = O(o(qo, Y). a) ::: O({PI, .... Pj}, a)
By definition of o~
(3.7)
Hence.
O'(q(;. yay = o/(o/(q'o. y), a) = O'([PI . ... , Pi], a)
by (3.6)
::: [rl' .... rd
by (3.7)
Thus we have proved (3.5) for x = .va.
By induction. (3.5) is true for all strings x. The other part (i.e. the 'only if'
part), can be proved similarly, and so (3.4) is established.
Now. x E T(M) if and only if O(q. x) contains a state of F. By (3.4).
8(qo, x) contains a state of F if and only if 8'(qo, x) is in F'. Hence. x E T(M)
if and only if x E T(Af'). This proves that DFA M' accepts L. I
Vote: In the construction of a deterministic finite automaton M 1 equivalent to
a given nondetelministic automaton M, the only difficult part is the construction
of 8/ for M j • By definition.
k
8'([q1 ... qd, a) = U 8(q;, a)
l=l
So we have to apply 8 to (q;. a) for each i = 1. 2..... k and take their
union to get o'([q] .. , qd. a).
When 8 for /1'1 is given in telms of a state table. the construction is simpler.
8(q;, a) is given by the row corresponding to q; and the column corresponding
to a. To construct 8'([ql ... qk]. a), consider the states appearing in the rows
corresponding to qj
, ql;o and the column corresponding to a. These states
constitute 8'([q]
qd. a).
Note: We write 8' as 8 itself when there is no ambiguity. We also mark the
initial state with ~ and the final state with a circle in the state table.
EXAMPLE 3.6
Construct a deterministic automaton equivalent to
M ::: ({qo. qd· {O. l}. 8, qo, {qoD
where 8 is defined by its state table (see Table 3.2).