Theory of Computation

Question 1

(a) (4 marks) NFA: $Q=\{q_0,q_1,q_2,q_3\}$, $\Sigma=\{a,b\}$, start $q_0$, $F=\{q_3\}$. $\delta(q_0,a)=\{q_0,q_1\},\ \delta(q_0,b)=\{q_0\},\ \delta(q_1,b)=\{q_2\},\ \delta(q_2,a)=\{q_3\},\ \delta(q_3,a)=\{q_3\},\ \delta(q_3,b)=\{q_3\}.$ Idea: stay in $q_0$ (self-loop on $a,b$) guessing where $aba$ starts; $q_1$ after $a$, $q_2$ after $ab$, $q_3$ after $aba$ then loop. Marks: correct states/start/final (2), transitions realizing "contains $aba$" (2).

(b) (6 marks) Subset construction from start $\{q_0\}$:

Accepting DFA states = those containing $q_3$: $\{D,E,F\}$. Start $A$. Marks: correct start & closure procedure (2), correct table (3), correct accepting set (1). (Once $q_3$ reached, all reachable subsets contain $q_3$ — a dead-accepting sink region, as expected for "contains substring.")

(c) (3 marks) $r = (a\mid b)^*\,aba\,(a\mid b)^*$. Justification: $(a\mid b)^*$ before and after matches arbitrary prefix/suffix; the literal $aba$ forces the required substring — exactly the strings containing $aba$. Kleene's theorem guarantees RE ⇔ FA equivalence. Marks: RE (2), justification (1).

(d) (7 marks) Pumping lemma (regular): If $M$ is regular, $\exists p\ge1$ s.t. every $w\in M$ with $|w|\ge p$ can be written $w=xyz$ with (i) $|xy|\le p$, (ii) $|y|\ge1$, (iii) $xy^iz\in M$ for all $i\ge0$. (2 marks)

Assume $M$ regular with pumping length $p$. Choose $w=a^p b^p a^p\in M$, $|w|=3p\ge p$. (1) By (i)–(ii), $xy$ lies within the first $p$ symbols, all $a$'s, so $y=a^k$ with $1\le k\le p$, and $y$ is a prefix-block of the first $a^p$. (2) Pump $i=2$: $xy^2z=a^{p+k}b^p a^p$. Now the count of leading $a$'s is $p+k\ne p$ (since $k\ge1$), while the trailing block is still $a^p$; a member of $M$ requires the first and last blocks equal to the middle-count $p$. Hence $xy^2z\notin M$. (2) Contradiction ⇒ $M$ is not regular. $\blacksquare$ (Deduct if wrong string chosen, e.g. one that pumps within a single equal block trivially.)

Question 2

(a) (5 marks) Grammar (union of two CFLs): $S\to S_1 \mid S_2,\quad S_1\to A\,C',\ A\to aAb\mid\varepsilon,\ C'\to cC'\mid\varepsilon,\quad S_2\to A'\,B,\ A'\to aA'\mid\varepsilon,\ B\to bBc\mid\varepsilon.$ Here $S_1$ gives $i=j$ (with free $k$ via $C'$), $S_2$ gives $j=k$ (with free $i$ via $A'$). (3 marks for correct grammar)

Leftmost derivation of $aabbcc$ (use $S_1$, $i=j=2,k=2$): $S\Rightarrow S_1\Rightarrow AC'\Rightarrow aAbC'\Rightarrow aaAbbC'\Rightarrow aabbC'\Rightarrow aabb\,cC'\Rightarrow aabb\,ccC'\Rightarrow aabbcc.$ (1)

Leftmost derivation of $abcc$ (use $S_2$, $i=1$, $j=k=...$ wait need $j=k$; here $j=1,k=2$? $abcc$: $i=1,j=1,k=2$, so $j=k$ fails; use $S_1$ with $i=j=1$, $k=2$): $S\Rightarrow S_1\Rightarrow AC'\Rightarrow aAbC'\Rightarrow abC'\Rightarrow ab\,cC'\Rightarrow ab\,ccC'\Rightarrow abcc.$ (1)

(b) (7 marks) $S\to aSb\mid\varepsilon$. Step 1 — Nullable: $S$ is nullable. Add new start $S_0\to S\mid\varepsilon$; remove $\varepsilon$ from $S$: from $S\to aSb$ removing nullable $S$ gives $S\to aSb\mid ab$. So $S_0\to S\mid\varepsilon$, $S\to aSb\mid ab$. (2) Step 2 — Unit productions: $S_0\to S$ replaced by $S$'s bodies: $S_0\to aSb\mid ab\mid\varepsilon$. Keep $\varepsilon$ only on start (allowed). (2) Step 3 — Terminals to variables: $A\to a$, $B\to b$. Rewrite: $S_0\to A S B\mid A B\mid\varepsilon$, $S\to A S B\mid A B$. (1) Step 4 — Break long RHS ($ASB$ length 3): introduce $C\to SB$: $S_0\to A C\mid AB\mid\varepsilon$, $S\to AC\mid AB$, $C\to SB$, $A\to a$, $B\to b$. (2) This is CNF (each production: variable→two variables, or variable→terminal, plus $S_0\to\varepsilon$).

(c) (8 marks) Pumping lemma (CFL): if $L_2$ is context-free, $\exists p$ s.t. every $w\in L_2$, $|w|\ge p$, factors as $w=uvxyz$ with (i) $|vxy|\le p$, (ii) $|vy|\ge1$, (iii) $uv^ixy^iz\in L_2$ for all $i\ge0$. (2)

Take $w=a^p b^p c^p$, $|w|=3p\ge p$. Since $|vxy|\le p$, the window $vxy$ spans at most two of the three symbol-blocks (it cannot touch both the $a$-block and $c$-block, which are $\ge p$ apart). (2) Case analysis on pump $i=2$ (or $i=0$): (3)

• $vy$ contains only $a$'s and/or $b$'s (no $c$): pumping changes $a$ and/or $b$ counts but $c$-count stays $p$; equality of all three counts breaks.
• $vy$ contains only $b$'s and/or $c$'s (no $a$): $a$-count stays $p$ while others change — breaks.
• $v$ or $y$ straddles a boundary and contains two distinct letters: $uv^2xy^2z$ has letters out of order ($\ldots b a\ldots$ or $\ldots c b\ldots$), leaving $a^*b^*c^*$ — not in $L_2$. In every case $uv^2xy^2z\notin L_2$, contradicting (iii). (1) Hence $L_2$ is not context-free. $\blacksquare$

Question 3

(a) (7 marks) $HALT_{TM}=\{\langle M,w\rangle : M\text{ halts on }w\}$. (1) Proof: suppose decider $H$ decides $HALT$: $H(\langle M,w\rangle)$ accepts iff $M$ halts on $w$, rejects otherwise (always halts). (1) Build $D$ on input $\langle M\rangle$: run $H(\langle M,\langle M\rangle\rangle)$; if $H$ says "$M$ halts on $\langle M\rangle$", then $D$ loops forever; if $H$ says "does not halt", then $D$ halts. (2) Now run $D$ on $\langle D\rangle$: (2)

• If $D$ halts on $\langle D\rangle$, then $H$ reported "halts", so by construction $D$ loops — contradiction.
• If $D$ loops on $\langle D\rangle$, then $H$ reported "does not halt", so $D$ halts — contradiction. Both cases contradictory ⇒ no such $H$ exists ⇒ $HALT_{TM}$ undecidable. $\blacksquare$ (1)

(b) (5 marks) Rice's theorem: Let $P$ be any property of the languages recognized by TMs (a semantic property: depends only on $L(M)$, not on $M$'s encoding) that is non-trivial (some TM's language has $P$, some doesn't). Then $\{\langle M\rangle : L(M)\in P\}$ is undecidable. (2) Application: "$L(M)=\varnothing$" is a semantic property (depends only on $L(M)$) and non-trivial (some machines recognize $\varnothing$, others recognize $\Sigma^*\ne\varnothing$). Hence by Rice's theorem $L_{\text{empty}}$ is undecidable. (3) (Note: $L_{\text{empty}}=E_{TM}$; Rice applies since the property is semantic & non-trivial — full credit for correctly invoking it. It is in fact co-recognizable but not decidable.)

(c) (4 marks) $A\le_m B$: there is a total computable $f:\Sigma^*\to\Sigma^*$ with $x\in A \iff f(x)\in B$ for all $x$. (1.5) Proof: if $B$ decidable by $D_B$ and $f$ computable, then decide $A$ by: on $x$, compute $f(x)$, run $D_B(f(x))$, and accept iff it accepts. This halts (both stages halt) and is correct by the reduction property. So $A$ decidable. (1.5) Contrapositive used for undecidability: if $A\le_m B$ and $A$ is undecidable, then $B$ is undecidable. (1)

(d) (4 marks) NP-complete: $L$ is NP-complete if (1) $L\in NP$ and (2) every $L'\in NP$ satisfies $L'\le_p L$ (polynomial-time many-one reduction). (1) $3\text{-SAT}\le_p\text{CLIQUE}$: Given a 3-CNF $\phi$ with $m$ clauses, build graph $G$: for each clause create 3 vertices, one per literal. Put an edge between two vertices iff they are in different clauses and their literals are not complementary (not $x$ and $\lnot x$). Set $k=m$. (2) Correctness: $\phi$ satisfiable $\iff$ $G$ has a $k$-clique. A satisfying assignment picks one true literal per clause; these $m$ literals are pairwise non-contradictory and in distinct clauses ⇒ pairwise adjacent ⇒ $m$-clique. Conversely a clique of size $m$ must use exactly one vertex from each clause (edges only cross clauses) with mutually consistent literals, yielding a satisfying assignment. Construction is polynomial. (1)

[
  {"claim":"Q1 NFA subset construction: transitions from B={q0,q1} on b give C={q0,q2}",
   "code":"B={'q0','q1'}\ndelta={('q0','a'):{'q0','q1'},('q0','b'):{'q0'},('q1','b'):{'q2'}}\nres=set()\nfor s in B:\n    res|=delta.get((s,'b'),set())\nresult = res=={'q0','q2'}"},
  {"claim":"Q1(d) pumping: p=3 sample, pumping y=a^k in first block breaks a-count equality",
   "code":"p=3; k=1\nfirst=p+k; middle_b=p; last=p\nresult = (first!=p) and (first!=last)"},
  {"claim":"Q2 CNF: number of variables after conversion of S->aSb|eps is 5 (S0,S,C,A,B)",
   "code":"vars={'S0','S','C','A','B'}\nresult = len(vars)==5"},
  {"claim