CS 288 Exam #1: Theory of Computation
1. What is wrong with the following "proof"?
"Theorem:" If A is a finite
alphabet and L is a finite
subset of A*, then L is not regular.
"Proof". Let n be the constant
from the pumping lemma and w = xyz with |xy| ≤ n, |y| ≥ 1.
Then xykz in L for
all k ≥ 0. But since |y| ≥ 1, that is an infinite set,
contradicting that L is finite.
Therefore, L cannot be
regular.
2. Are finite sets of strings regular languages? Prove or disprove.
3. Consider the property P of
a language L: All strings in L
have even length.
a. Is P decidable? Prove or
disprove.
b. Is P recursively
enumerable? Prove or disprove.
4. Consider the same property P,
but now applied only to regular
languages (defined by a DFA, not a Turing machine). Is the property now
decidable? If so, outline a decision procedure. If not, prove your
assertion.
5. The Java virtual machine (JVM) loads bytecodes and verifies certain properties before executing the instructions.
For example, it checks that no uninitialized variables are being
accessed. If these verifications fail, the virtual machine refuses to
execute the instructions. However, this seems to conflict with Rice's
theorem. If P is the property { M | M is a Turing machine that never
reads an uninitialized tape symbol }, then this is a nontrivial property
and hence undecidable. Explain why the JVM verifier doesn't actually
conflict with Rice's theorem. Hint:
As you probably know from your own Java programming experience, the
Java compiler makes a similar
promise but doesn't quite live up to it.
6. The 0/1 INTEGER PROGRAMMING PROBLEM is the following: Given a set of
linear constraints of the form
ci ≤ ∑j=1n aijxj ≤ di
where the aij, ci and di are integers, and x1...xn are variables, does
there exist an assignment of 0 or 1 to each of the variables that makes
all the constraints true?
a. Show that the 0/1 INTEGER PROGRAMMING PROBLEM is in NP.
b. Show how the following specific
instance of 3-SAT can be reduced to an instance of the 0/1 INTEGER
PROGRAMMING PROBLEM.
(x1 + x2-1 + x4-1)(x1-1 + x3-1 + x4-1)(x2-1 + x3-1 +x4), where x-1 denotes the Boolean
complement of x
c. Show that the 0/1 INTEGER PROGRAMMING PROBLEM is NP complete by
reducing it from 3-SAT. Your reduction should show how to transform a
generic instance of 3-SAT with r variables
and s clauses of the form
∏i=1s (xti1ei1 + xti2ei2 + xti3ei3)
where tij ∈ { 1 . . . r }and eij
∈ { 1, -1 }
Be as specific as possible. What are the variables of the 0/1 INTEGER
PROGRAMMING PROBLEM? What are the aij,ci and di?