Formal languages and theory of computation, part 2, CS 288, May 2, 2007

Each of the three questions is worth 20 points

Find a context-free grammar for the language L(M) that is accepted by the DFA below. The start symbol for M is q₀ and the alphabet is {0, 1, b, -, .}.
The class of nondeterministic finite automata does not accept any more languages that the class of deterministic finite automata.
1. Is this statement still true if "pushdown automata" replaces "finite automata"?
2. Is the statement still true if "Turing machines" replaces "finite automata"?
3. For a given NFA with n states, give an upper bound on the number of states that an equivalent DFA can have. Express your answer in O-notation, as a function of n.
4. If a given NFA requires time t to accept an input string, give an upper bound on the amount of time required for the equivalent DFA to recognize the string. Express your answer in O-notation, as a function of t.
The subgraph isomorphism problem takes as an instance two undirected graphs G and S, and asks whethere there is a subgraph of G that is isomorphic to S. Show that the subgraph isomorphism problem is NP-complete. Don't forget to show that the problem is in NP (doing this is worth 5 points). You may assume that a graph with n vertices has a representation of size at least n. You may also assume that the clique problem is NP-complete, where an instance of the clique problem consists of an undirected graph G and a nonnegative integer k, and the question is whether there is a subset C of the vertices of G of size at least k such that every vertex is C is adjacent (in G) to every other vertex of C.
Don't confuse the subgraph isomorphism problem with the graph isomorphism problem, which is not known to be NP-complete.