This page is located at http://www.cs.bc.edu/~alvarez/Theory/PS2/ps2.sol.html
We will solve the more general problem of constructing a DFA that recognizes the intersection of two regular languages. Suppose you have two DFA's M_{1} and M_{2}. For each of these machines, assume you know the five ingredients (Q_{i}, Σ_{i}, δ_{i}, q0_{i}, F_{i}) of the formal definition, where i is either 1 or 2 as appropriate for each machine. Assume that both machines have the same input alphabet Σ, that is, that Σ_{1}=Σ_{2}=Σ. We wish to build a DFA that recognizes the intersection of the two DFA-regular languages L(M_{1}) and L(M_{2}). We'll use the Cartesian product idea discussed in class for the case of the union of two DFA-regular languages. The point is that we still wish to do a parallel simulation of the two machines. So, we define the following ingredients for the new machine:
δ | a | b |
S | {S, A} | {S} |
A | Φ | {B} |
B | Φ | Φ |
a) Draw the state diagram of the NFA N. Mark the start state with a dangling incoming arrow, the accepting states with double circles, and each transition with an arrow labeled by the input symbols associated with that transition.
b) Describe all possible computations of N on the input string abaaab, by drawing the appropriate computation tree. Label each arc in the computation tree with the input symbol that mediates the corresponding transition. Label each leaf with the final result of the computation corresponding to that particular branch of the tree: accepts, rejects, or fails prematurely.
S a / \ S A b | | S B a / \ S A a / \ S A a / \ S A b | | S BAny branches that have fewer than 6 arcs are non-accepting, as they fail to process the full input string. This leaves only two full-length branches, neither of which ends in an accepting state. Therefore, there are no accepting computations in the computation tree of N on input abaaab.
c) Is the string abaaab in the language L(N)? Explain your answer concisely in terms of the set of possible computations of N with this string as its input, as described in the previous part of this task.
a | b | |
empty set | empty set | empty set |
{S} | {S, A} | {S} |
{A} | empty set | {B} |
{B} | empty set | empty set |
{S, A} | {S, A} | {S, B} |
{S, B} | {S, A} | {S} |
{A, B} | empty set | {B} |
{S, A, B} | {S, A} | {S, B} |
b) What states of the DFA M in part a) are unreachable? Explain. Give the reduced state diagram obtained by removing all unreachable states of M.