CMPSC 464 Spring 2019 Final exam practice questions
1. Give an example of a language that is
(a) regular
(b) context free, but not regular
(c) decidable, but not context free (d) recognizable, but not decidable
(e) unrecognizable
(f) unrecognizable and has unrecognizable complement
(g) decidable and mapping reducible to its own complement (h) in NPSPACE bot not in PSPACE
2. True/False/Unknown
For questions with ( T F U ), specify whether the claim is True, False, or Unknown.
T F U FACTORING ∈ P.
T F U There is a problem in NP that has a polynomial-time algorithm. T F U ATM reduces to SAT.
T F U TQBF is NP-hard.
T F If problem A reduces to problem B, and B is NP-complete, then A is NP-complete. TF IfL1 ≤P L2 andL2 ≤P L1,thenL1 =L2.
T F For every i, the language Li = {aibici} is context free.
3. What is wrong with the “proof” below of the following claim? Claim: Let L be regular. Then L′ = {ww : w ∈ L} is regular.
Proof: We know that the concatenation of two regular languages is regular. Since L′ = L ◦ L, it follows that L′ must also be regular.
4. Let L be any language that is not Turing-recognizable. Define the language L′ = {x|(x has odd length and x ∈ L) or (x has even length and x ∈/ L)}.
Show that L′ and its complement L′ cannot both be Turing-recognizable.
5. Prove or disprove that the following language is in PSPACE:
N = {⟨M⟩|M is an NFA with L(M) ̸= Σ∗ where Σ is the alphabet of M}.
6. Suppose you have an algorithm which tells you whether or not a graph has a Hamil- tonian Path in polynomial-time. Show how to use this to develop a polynomial-time algorithm for Hamiltonian Path, i.e., returns a path if one exists.
1
7. A subset of the nodes of a graph G is a dominating set if every other node of G is adjacent to some node in the subset. Let
DOMINATING-SUBSET = {⟨G, k⟩|G has a dominating set with k nodes}.
Show that it is NP-complete. Hint: You may assume that VERTEX-COVER is NP- complete.
2