4–5 claims spanning ALL topics. For each: state “True” or “False”, then give a proof (if true) or counterexample + explanation (if false).
This is the hardest question to drill because it tests breadth. No single exercise prepares you — only genuine understanding of all weeks. But the claim types are predictable.
DFA/NFA: “Every regular language can be accepted by a DFA with at most 5 states” (False — 24–25 end Q10a). “Every NFA N has an equivalent NFA N′ without epsilon edges” (True — 24–25 resit Q10a).
CFG/CFL: “Every grammar with at most 2 rules has a finite language” (False — 24–25 resit Q10b).
Reductions/Recognizability: “If A ≤m B, A is TR, and B is co-TR, then B is decidable” (False — 24–25 resit Q10c). “There is a mapping reduction EQTM ≤m ATM” (False — 23–24 end Q10b).
Complexity: “If L ∈ P, then L ∈ TIME(n)” (False — 24–25 resit Q10d). “{x | last symbol of x is a vowel} ∈ TIME(1)” (True — 24–25 end Q10c).
Karp reductions: “DMST ≤P Vertex Cover” (True — 24–25 resit Q10e). “L(D) ≤P L(G) for any DFA D and CFG G” (False — 24–25 end Q10d).
Mixed: “M is a decider” given conditions on L(D)=A, L(M)=B, C ≤ A and B ≤ C (False — 23–24 end Q10a).
Regular Languages
Context-Free Languages
Decidability & Recognizability
| Problem | Decidable? | TR? | co-TR? |
|---|---|---|---|
| ADFA, ANFA, ACFG | Yes | Yes | Yes |
| EDFA, ECFG | Yes | Yes | Yes |
| EQDFA | Yes | Yes | Yes |
| ATM | No | Yes | No |
| HALTTM | No | Yes | No |
| ETM | No | No | Yes |
| EQTM | No | No | No |
Mapping Reduction Rules
Complexity
Karp Reduction Rules
“Every regular language can be accepted by a DFA with at most 5 states.”
Answer: False
Counterexample: L = {ak | 0 ≤ k ≤ 100} over Σ = {a} is finite, hence regular. But a DFA must distinguish between reading 0, 1, 2, …, 100, and 101+ symbols of ‘a’, requiring at least 102 states. Any finite language is regular, and we can make it require arbitrarily many states.
“Every NFA N has an equivalent NFA N′ (L(N) = L(N′)) without epsilon edges.”
Answer: True
The subset construction converts any NFA to an equivalent DFA, which has no ε-edges. Every DFA is trivially an NFA. So N′ = the DFA from subset construction is an NFA with L(N′) = L(N) and no ε-edges. ∎
“Every grammar with at most 2 rules has a finite language.”
Answer: False
Counterexample: S → aS | ε. This grammar has exactly 2 rules and generates L = {an | n ≥ 0} = a*, which is infinite.
“For all languages L it holds that: {x | x is a palindrome} ≤m L.”
Answer: False
Counterexample: Let L = ∅. The reduction requires every palindrome to map to some string in L. But L = ∅ contains nothing, so no function f can satisfy: x is a palindrome ⇒ f(x) ∈ ∅.
General principle: A ≤m B requires yes-instances of A to map to yes-instances of B. If B = ∅, there are no yes-instances, so any nonempty A fails.
“If A ≤m B and A is Turing-recognizable and B is co-Turing-recognizable, then B is decidable.”
Answer: False
A ≤m B with A being TR tells us nothing about B — recognizability transfers downward (B recognizable ⇒ A recognizable, not the other way). We are given B is co-TR, but we have no reason to conclude B is also TR. Without both TR and co-TR, B is not necessarily decidable.
Concrete situation: B could be ETM (co-TR but not TR, hence undecidable), and A could be any decidable language with A ≤m ETM. The conditions are satisfied but B is undecidable.
“There is a DFA D, TM M, and languages A, B, C where L(D)=A, L(M)=B, C ≤m A and B ≤m C. Claim: M is a decider.”
Answer: False
L(D) = A is regular, hence decidable. C ≤m A and A decidable ⇒ C is decidable. B ≤m C and C decidable ⇒ B = L(M) is decidable.
So L(M) is decidable — but M itself need not be a decider. A decider must halt on all inputs. M could be a recognizer that happens to recognize a decidable language without itself halting on all inputs.
Counterexample: Let M accept {a} by halting on input “a” but looping forever on all other inputs. L(M) = {a} is decidable, but M is not a decider.
“There is a mapping reduction from EQTM to ATM.”
Answer: False
EQTM is not Turing-recognizable (neither TR nor co-TR). ATM is TR. If EQTM ≤m ATM existed, then since ATM is TR, EQTM would be TR (recognizability transfers downward). But EQTM is not TR. Contradiction.
“{x | the last symbol of x is a vowel} ∈ TIME(1).”
Answer: True
The exam convention treats TIME(1) as meaning the TM only needs to inspect the last symbol. A TM can be designed that, upon reading each symbol, stores it in finite-state control. When it reaches a blank (end of input), it accepts or rejects based on the last stored symbol.
On a standard single-tape TM, scanning to the end takes O(n) time, so formally this language is in TIME(n), not TIME(1). The exam key says True. The intended reading is that only one “meaningful comparison” is needed — the answer depends on a single symbol. On this exam, answer True. A fully rigorous TIME(1) argument would require a 2-tape TM (write input on tape 2 in reverse, read one cell) or a random-access model, but the exam uses a relaxed interpretation.
“If L ∈ P, then L ∈ TIME(n).”
Answer: False
P = ∪k TIME(nk). A language in TIME(n3) is in P but not necessarily in TIME(n). By the time hierarchy theorem, TIME(n) ⊊ TIME(n2) ⊊ TIME(n3) ⊊ …, so there are languages in P that provably require more than linear time.
“Consider a DFA D and CFG G. There must be a Karp reduction: L(D) ≤P L(G).”
Answer: False
Counterexample: Let D be a DFA with L(D) = {a} (nonempty) and G be a CFG with L(G) = ∅. The reduction requires: x ∈ L(D) ⇒ f(x) ∈ L(G). But L(G) = ∅ has no members, so we cannot map the yes-instance “a” anywhere.
The claim says “must” for any DFA and CFG — but it fails when L(D) is nonempty and L(G) is empty. (Also fails when L(D) ≠ Σ* and L(G) = Σ*.)
“DMST ≤P Vertex Cover” (DMST = Decision Minimum Spanning Tree, known to be in P).
Answer: True
DMST ∈ P. Any language in P Karp-reduces to any nontrivial language (not ∅ or Σ*). Vertex Cover is nontrivial. So DMST ≤P VC.
Construction: Let D be a TM that decides DMST in poly time. On input x: run D on x. If D accepts, output a known yes-instance of VC. If D rejects, output a known no-instance. This runs in poly time, and x ∈ DMST ⇔ f(x) ∈ VC. ∎
“Every DFA with n states can accept at most n−1 distinct strings.”
False. A DFA can accept infinitely many strings. Example: a 2-state DFA over {a} where q0 is the start and accept state, with δ(q0, a) = q0. This accepts a* = {ε, a, aa, aaa, …} — infinitely many strings from just 2 (or even 1) states.
“If L is regular and L′ is context-free, then L ∩ L′ is context-free.”
True. CFLs are closed under intersection with regular languages. Construct a PDA for L′ and run a DFA for L in parallel within the finite control. The combined machine is a PDA recognizing L ∩ L′. ∎
“The complement of every context-free language is context-free.”
False. CFLs are not closed under complement. If they were, then by De Morgan’s law (A ∩ B = complement(complement(A) ∪ complement(B))) and closure under union, they would be closed under intersection. But CFLs are NOT closed under intersection: L1 = {aibjck | i = j} and L2 = {aibjck | j = k} are both CFL, but L1 ∩ L2 = {anbncn} is not CFL. Contradiction.
“If A ≤m B and B is decidable, then A is Turing-recognizable.”
True. A ≤m B and B decidable ⇒ A decidable. Every decidable language is TR. So A is TR. ∎
“ATM ≤m ĀTM”
False. By the complement rule: A ≤m B ⇔ Ā ≤m B̄. So ATM ≤m ĀTM would imply ĀTM ≤m ATM. Since ATM is TR, that would make ĀTM TR. But ĀTM is not TR. Contradiction.
“HALTTM ≤m ETM”
False. HALTTM is TR but not co-TR (since it is undecidable and TR + co-TR = decidable). ETM is co-TR. If HALTTM ≤m ETM existed, then since ETM is co-TR, HALTTM would be co-TR. But HALTTM is not co-TR. Contradiction.
“If L ∈ NP and L ≤P 3SAT, then L is NP-complete.”
False. NP-completeness requires: (1) L ∈ NP, and (2) every NP problem reduces to L. The claim only shows L reduces TO 3SAT, not that anything reduces to L. Every language in P is in NP and reduces to 3SAT, but P problems are not NP-complete (unless P = NP).
“Every NP-hard problem is undecidable.”
False. 3SAT is NP-hard (in fact NP-complete) and decidable. NP-hard means “at least as hard as every NP problem” — this includes NP-complete problems, which are in NP and hence decidable. Undecidable problems are NP-hard too, but NP-hard does not imply undecidable.