Solutions -- formal languages and theory of computation, part 2, CS 288,
May 2, 2007

  1. If the nonterminal symbols A, B, C, D, E are used respectively for q0 through q4, then a regular grammar for L(M) can be constructed directly from M -- this grammar would have start symbol A and productions
         A → -B | 0C | 1C
     B → 0C | 1C
     C → 0C | 1C | bE | .D
     D → 0D | 1D | bE
     E → ε
    Other answers are possible, perhaps by noting that L(M) = L(r) for the regular expression
    r = (ε + -)(0+1)(0+1)*[ε + .(0+1)*]b

    One grammar based on this observation would have start symbol B and productions

         B → U | -U
     U → Sb | S.b | S.Sb
     S → 0 | 1 | 0S | 1S
     

    1. No. See p. 255 of Hopcroft et al for an example of a language that's accepted by a PDA but not a DPDA.

    2. Yes, by Theorem 8.11 of Hopcroft et al.

    3. The worst-case number of states is Θ(2n), since states of the equivalent DFA correspond to subsets of states of the orginial NFA.

    4. Since table lookup in the DFA still takes time O(1), the time required for the DFA to recognize the string is still proportional to the length of the string. So it is also O(t). In other words, for Turing machines the time required may increase exponentially when nondeterminism is added, while for finite automata it's the space and not the time that may increase exponentially.

     

  3. To show that the clique problem is polynomially reducible to the subgraph isomorphism problem, let G be the graph component of a clique instance I and let k be the size of the clique to be sought. Let T(I) be the pair (G,S), where S is the complete graph on k vertices. That is, for every pair (u,v) of vertices of S is connected by an edge, there is an edge (u,v) in S. It follows directly from the definition of a clique that G has a clique of size k iff it has a subgraph isomorphic to S, so I and T(I) are equivalent. Construction of T(I) takes time O(n2), where n is the number of vertices in G. By our assumptions, this time is polynomial in the size of I.

    The subgraph isomorphism problem is in NP, since for each vertex in S one may guess the corresponding vertex in G. If |S| and |G| are the number of vertices in S and G respectively, this requires |S| guesses of at most lg |G| bits each. That edges exist between corresponding vertices in G iff they exist between the original vertices in S requires |S|2 lookups in an adjacency matrix or adjacency list. In each case, as well as for showing that the guessed vertices are all distinct, the amount of work required is polynomial in the size of the instance, which under our assumptions is at least |G| + |S|.

    Note that showing NP-completeness of the clique problem is relatively easy -- it was part of last year's exam.