CS385, Fall 2010
Theory of Computation
Problem Set 2 Solutions

This page is located at http://www.cs.bc.edu/~alvarez/Theory/PS2/ps2.sol.html

  1. Design a DFA that recognizes the language of all strings over the alphabet {a, b} that contain the substring ba and exactly two a's (including the one in ba). Provide the state transition diagram, as well as the five ingredients in the formal definition of DFA. Hint: try to carry out the construction by combining two machines, one for each part of the above description of the language.

    Solution

    The target language is described as the intersection of two languages A and B over the same language {a,b}. The language A consists of all strings that contain ba as a substring, and the language B consists of all strings that contain exactly two a's. Notice that each of the languages A and B is regular, since you can construct a DFA that recognizes A and another DFA that recognizes B.

    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 M1 and M2. For each of these machines, assume you know the five ingredients (Qi, Σi, δi, q0i, Fi) 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(M1) and L(M2). 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:

    • Q = Q1 x Q2
    • Σ = same as for either of the two machines
    • δ = δ1 x δ2, that is, δ( (q,q'), s ) = ( δ1(q,s), δ2(q',s) ) for all states q in Q1 and q' in Q2 and all symbols s in Σ.
    • q0 = (q01,q02)
    The only difference lies in the choice of the set of final states. Since in the current context a string should be accepted only if it belongs to the language L(M1) and also to the language L(M2), we take as the set of final states the set of all pairs (q,q') consisting of an accepting state of the first machine paired with an accepting state of the second machine. In terms of Cartesian products, we can write:
    • F = F1 x F2
    What specific machine does this construction yield for the two languages described in the statement?

  2. Consider the NFA N that has the state transition function δ given by the table below, with start state S and set of accepting states {A}. The symbol Φ denotes the empty set.
    δ 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.

    Solution

    We discussed this in class. The NFA has three states, S, A, B. S is identified as the start state, and B is identified as an accepting state. The start state S has a self loop labeled a,b. There is a transition from S to A labeled a. There is a transition from A to B labeled b.

    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.

    Solution

    We discussed this in class. Here is a text-only summary: 
    					S
a				/		\
				S		A
b				|		|
				S		B
a			/		\
			S		A
a		/		\
		S		A
a	/		\	
	S		A
b	|		|
	S		B
    Any 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.

    Solution

    No, abaaab is not in the language L(N), as by the previous part of this task, there are no accepting computations in the computation tree for abaaab in N. Notice that all strings in L(N) end in a, since the only transition entering the accepting state is an a-transition.

  3. a) Use the construction described in the proof of the equivalency of NFA's and DFA's discussed in class to convert the NFA N of the preceding problem to a DFA M that recognizes the same language as N. Give the state transition diagram of the resulting DFA M. Each state of M should be labeled with the set of subsets of N that corresponds to it. All states resulting from the construction should be shown, regardless of whether they are reachable or not.

    Solution

    The subset construction yields a DFA M with exactly 8 states, corresponding to all subsets of the original NFA N's state space. Thus, the state space of M contains the 8 states Φ, {S}, {A}, {B}, {S,A}, {S,B}, {A,B}, {S,A,B}. The start state is {S} and the final states are all those that contain M's unique accepting state A in their labels ({A}, {S,A}, {A,B}, {S,A,B}). The transition table of M appears below.
    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.

    Solution

    The unreachable states are those that cannot be reached from the start state {S} by a sequence of transitions. In the present case, all states except {S} and {S,A} are unreachable. After removing the unreachable states, we are left with a very simple two-state DFA that has a b-self-loop at {S}, an a-transition from {S} to {S,A}, a b-transition from {S,A} to {S}, and an a-self-loop at {S,A}.