2.2 Examples of DFA ‘s 35
0 a
0 C
Figure 2.15: The second solution to Example 2.13.Solution 2. We can also use the checker method of Example 2.8 to construct
a DFA for this set. First, we note that if a string x has a substring 00 and a
suffix 01, then the occurrence of 00 must come before that of 01. So, we set
up the two checkers as shown in Figure 2.15(a) and 2.15(b). Intuitively, states
qo,qr and 42 are like those in Figure 2.9. State q3 means that “substring 00 has
been found and no prefix of 0 1 is found,” and state q4 means that “substring
00 has been found and prefix 0 of 01 has also been found.” Note that the
out-edges from state q2 are not determined yet, since finding the substring 00
does not imply the string being accepted.
Now we add additional edges to the checkers as in Examples 2.8 and 2.10.
It is easy to see that we need to define 8(qo, 1) = S(q1,l) = qo, since we are
still at the first stage of checking substring 00.
Next, we have 6(q2,1) = 45, which is a final state, since, at state 42, we
have just seen a substring 00 and the second 0 plus the new symbol 1 form
the required suffix 01. We also let S(a2,O) = q4, since q4 is the state at which
stubstring 00 has been found and a symbol 0 has just been read.
The actions at states q3, q4 and q5 are just like those in Figure 2.11. That
is, we add
qa3,1> = q3, S(a4,o) = !I47
gas, 0) = q4, S(a5,l) = q3*
The complete DFA is shown in Figure 2.15(c).
Note that, in Solution 1, the number of states in the product DFA A4 is,
in general, the product of the number n1 of states in Mr and the number n2
of states in A&. In Solution 2 here, the number of states is, in general, only