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

Each of the three questions is worth 20 points

 

  1. Give an example, if possible, of
    1. a problem in the class PS that does not reduce in polynomial time to the Quantified Boolean Formula (QBF) problem.
    2. a language that is accepted by a nondeterministic Turing machine but not by a deterministic Turing machine.
    3. a language that is accepted by a Turing machine, but not by any Turing machine that halts on all its inputs.
    4. two context-free languages whose intersection is not context-free.
    Give a one-sentence justification of each of your answers.

     

  2. Show that the regular expresssions 0(10)* and (01)*0 represent the same language.

     

  3. Recall that a node cover of a graph is a set of nodes such that each edge has at least one of its endpoints in the set. Determining whether a graph has a node cover of size at most j is NP-complete. The CLIQUE problem has as an instance a graph G and a positive integer k, and the question is whether there is a subset S of the nodes of the graph such that |S|=k and there is an edge between every two distinct nodes of S.
    1. Show that the CLIQUE problem is in NP. You may assume that the length of an instance is at least as large as n, where n=|V| and V is the set of nodes of graph G.
    2. Assuming the result of part 1, show that the CLIQUE problem is NP-complete (hint: consider reducing from the node cover decision problem described above, and consider letting G be the graph obtained from the graph G' in the node cover instance by letting {v,w} be an edge in G iff it is not an edge of G').