Level 1 — RecognitionTheory of Computation

Theory of Computation

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Time limit: 20 minutes
Total marks: 30
Instructions: Answer all questions. For True/False questions, a one-line justification is required for full marks.

Section A — Multiple Choice (1 mark each)

Q1. A DFA is formally defined as a 5-tuple. Which of the following is NOT one of its components?

(a) A finite set of states $Q$
(b) An input alphabet $\Sigma$
(c) A stack alphabet $\Gamma$
(d) A transition function $\delta$

Q2. In subset construction (NFA → DFA), each DFA state corresponds to:

(a) a single NFA state
(b) a subset of NFA states
(c) an $\varepsilon$ -transition
(d) a final state only

Q3. The language $L = \{a^n b^n \mid n \ge 0\}$ is:

(a) regular
(b) context-free but not regular
(c) not context-free
(d) not recognizable

Q4. Which normal form allows only productions of the form $A \to BC$ and $A \to a$ ?

(a) Greibach Normal Form
(b) Chomsky Normal Form
(c) Backus–Naur Form
(d) Kuroda Normal Form

Q5. The Halting Problem is:

(a) decidable
(b) undecidable but not recognizable
(c) undecidable but recognizable (recursively enumerable)
(d) regular

Q6. Rice's theorem states that any non-trivial property of the language recognized by a Turing machine is:

(a) decidable
(b) undecidable
(c) always true
(d) context-free

Q7. A problem is in class NP if:

(a) it can be solved in polynomial time deterministically
(b) a proposed solution can be verified in polynomial time
(c) it requires exponential space
(d) it is undecidable

Q8. Which of the following is known to be NP-complete?

(a) Sorting a list
(b) 3-SAT
(c) Shortest path (single source)
(d) Matrix multiplication

Q9. Cook's theorem established that the first problem proven NP-complete is:

(a) Vertex Cover
(b) SAT (Boolean satisfiability)
(c) TSP
(d) Halting Problem

Q10. A PDA differs from a finite automaton by having an additional:

(a) tape
(b) stack
(c) oracle
(d) second input head

Section B — Matching (5 marks total)

Q11. Match each language class with its recognizing machine model. Write pairs (i–?, etc.). (5 marks, 1 each)

Column A	Column B
(i) Regular language	(A) Turing machine
(ii) Context-free language	(B) Deterministic finite automaton
(iii) Recursively enumerable language	(C) Pushdown automaton
(iv) Complexity class verifiable in poly time	(D) NP
(v) Quantified Boolean Formula problem	(E) PSPACE

Section C — True / False with Justification (1.5 marks each: 0.5 answer + 1 justification)

Q12. The complement of a regular language is always regular.

Q13. Every NFA with $\varepsilon$ -transitions recognizes a language that no DFA can recognize.

Q14. The pumping lemma can be used to prove a language IS regular.

Q15. Non-deterministic Turing machines can recognize strictly more languages than deterministic Turing machines.

Q16. Every NP-hard problem must belong to NP.

Q17. A multi-tape Turing machine is strictly more powerful (recognizes more languages) than a single-tape Turing machine.

Q18. If $P = NP$ were proven, then problems like 3-SAT would have polynomial-time algorithms.

Q19. An approximation algorithm with ratio 2 for a minimization problem always returns a solution at most twice the optimal cost.

Q20. The set of Turing-recognizable languages is closed under complement.

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (c). A DFA has no stack; the 5-tuple is $(Q,\Sigma,\delta,q_0,F)$ . The stack alphabet $\Gamma$ belongs to a PDA. (1)

Q2 — (b). Subset construction builds DFA states from subsets of NFA states (power set), tracking all states the NFA could simultaneously be in. (1)

Q3 — (b). $a^n b^n$ fails the regular pumping lemma but is generated by CFG $S\to aSb\mid\varepsilon$ , so it is context-free but not regular. (1)

Q4 — (b). CNF permits exactly $A\to BC$ (two non-terminals) and $A\to a$ (single terminal). (1)

Q5 — (c). The Halting Problem is undecidable but recursively enumerable — a machine can simulate and accept if halting occurs, but cannot decide non-halting. (1)

Q6 — (b). Rice's theorem: every non-trivial semantic property of the recognized language is undecidable. (1)

Q7 — (b). NP = languages with a polynomial-time verifier for a polynomially-sized certificate. (1)

Q8 — (b). 3-SAT is a classic NP-complete problem; the others are in P. (1)

Q9 — (b). Cook (1971) proved SAT is NP-complete — the foundational result. (1)

Q10 — (b). A PDA = finite automaton + stack (unbounded LIFO memory). (1)

Section B

Q11 (5 marks, 1 each):

(i) – (B) Regular ↔ DFA
(ii) – (C) CFL ↔ PDA
(iii) – (A) RE ↔ Turing machine
(iv) – (D) verifiable in poly time ↔ NP
(v) – (E) QBF ↔ PSPACE (QBF is PSPACE-complete)

Section C (0.5 answer + 1 justification)

Q12 — TRUE. Swap accepting/non-accepting states in a complete DFA; regular languages are closed under complement. (1.5)

Q13 — FALSE. $\varepsilon$ -NFAs, NFAs and DFAs are all equivalent in expressive power (subset construction converts any NFA to a DFA). (1.5)

Q14 — FALSE. The pumping lemma gives only a necessary condition; it is used to prove NON-regularity by contradiction, never regularity. (1.5)

Q15 — FALSE. NTMs and DTMs recognize the same class of languages (a DTM can simulate an NTM by search); NTMs may only be faster. (1.5)

Q16 — FALSE. NP-hard means at least as hard as every NP problem; it need not be in NP (e.g., the Halting Problem is NP-hard but not in NP). (1.5)

Q17 — FALSE. Multi-tape TMs are equivalent to single-tape TMs in power; a single tape can simulate multiple tapes (with polynomial time overhead). (1.5)

Q18 — TRUE. 3-SAT is NP-complete, so $P=NP$ would put it in P, giving a polynomial-time algorithm. (1.5)

Q19 — TRUE. By definition, a 2-approximation for minimization guarantees cost $\le 2\cdot OPT$ . (1.5)

Q20 — FALSE. Recognizable (RE) languages are NOT closed under complement; if both $L$ and $\overline{L}$ were RE, $L$ would be decidable (e.g., Halting Problem is RE but its complement is not). (1.5)

[
  {"claim":"DFA 5-tuple has 5 components, not stack alphabet count 6", "code":"components = ['Q','Sigma','delta','q0','F']; result = (len(components)==5) and ('Gamma' not in components)"},
  {"claim":"Subset construction power set size for n NFA states is 2**n", "code":"n=3; dfa_states = 2**n; result = (dfa_states==8)"},
  {"claim":"CNF productions have RHS length 2 (nonterminals) or 1 (terminal)", "code":"valid = {2,1}; result = valid=={1,2}"},
  {"claim":"2-approximation bound: solution <= 2*OPT holds for OPT=10 giving bound 20", "code":"OPT=10; ratio=2; bound=ratio*OPT; result=(bound==20)"}
]