Problem Solving in Automata, Languages, and Complexity

34 FIN.TE AUTOMATA

Figure 2.14: Product DFA for Example 2.12.

For instance, the computation path of x = 0101 in this product automaton

is [qo, qo], [al, a117 [ao, a21, [al, a11 9 [Qo, azl l Furthermore, if 4i E F1 or 4j (5 F2,

then we let [qi, aj] E F. That is, F = (FI x Q2) U (QI x Fz).

From the above description, it is clear that M accepts the union of the

DFA’s Mr and A&. We show this product DFA M in Figure 2.14, where each

vertex with the label (i, j) denotes the state [qi, aj].

Two facts about this DFA are worth mentioning: First, since states [qo, al],

[Q1,Qol a-d b^1 4 2 1 are unreachable from the initial state [qo, 401~ we omitted

them in Figure 2.14. Second, states [aa, ql], [42, qo] and [aa, aa] can be merged

into a single success state, since all three states are final states and there is

no way to leave these three states once we get there. There are some general

techniques of simplifying DFA’s. We will discuss these techniques in Section

2.7.^0

The above method can also be applied to the problems of finding the inter-

sections or the differences of two languages which are accepted by DFA’s. All

we need is to construct the product DFA of the two given DFA’s and choose

different sets of final states. This method can also be generalized to construct

the product DFA of three, four, or any finite number of DFA’s.

Example 2.13 The set of all binary strings having a substring 00 and ending

with 01.

Solution 1. This language is the intersection of two languages (O+l)*OO(O+l)*

and (O+l)*Ol. In Example 2.12, we constructed a product DFA to accept the

union of these two languages. Here, we can use the same product DFA, except

that we will define the set F of final states to consist of states in which both

components are final states; that is, F = F1 x F2. The transition diagram

of the resulting DFA is just like that of Figure 2.14, except that the final set

consists of only one state [aa, q2].^0