Problem Solving in Automata, Languages, and Complexity

(^76) FINITE AUTOMATA
Figure Figure 2.47: 2.47: DFA DFA AL AL
d
Figure 2.48: Graph G.
qo 41 42 43 %
Figure 2.50: The table buildup
method for Example 2.53.
&lq-J
0 091
Figure 2.49: Minimum DFA of
Example 2.53.
For this example, we show the corresponding graph G in Figure 2.48. (We
only show vertices which are reachable from vertices not in U.) The vertex
(qd, as> is in U and is denoted by double circles. All vertices from which there
are paths going to a vertex in U have been marked with X. Thus, we have
40 Rf; ~1 and q2 RE q3. The resulting minimum DFA is shown in Figure 2.49.
0
Solution 2. In the above solution, the critical step is to determine, from a
given pair (qi, aj> of states, whether there is a path in G from it to a vertex
in U. This question can be solved using a table buildup method. We create a
table of pairs (ai, qj). Initially, we mark all pairs in U with value 0. At stage
Ic > 0, we mark each unmarked pair (qi, qj) with value k if there is an edge
from it to a pair with mark k - 1; that is, we mark pair (qi, qj) with value k if