Theory of Computation

Q1 (10)

(a) (2) $L(N)$ = all strings over $\{a,b\}$ containing the substring $ab$; equivalently strings whose penultimate-path requires an $a$ then $b$ reaching $q_2$. Since $q_2$ is a dead accept sink reached only via $q_0\xrightarrow{a}q_1\xrightarrow{b}q_2$, and $q_0$ loops on both letters, $L(N)=\Sigma^* ab$ — strings ending in $ab$? Check: after reaching $q_2$ there are no moves, so any further symbol kills the run. Accept exactly when input ends with $ab$. (Full 2 marks for "strings ending in $ab$"; 1 mark for "containing $ab$".)

(b) (6) No $\varepsilon$-transitions, so subsets are plain. Start $=\{q_0\}$.

Accept states = those containing $q_2$: $\{q_0,q_2\}$. (2 marks per row / correct transitions; deduct for missing accept marking.)

(c) (2) 3 reachable DFA states.

Q2 (10)

(a) (3) Pumping lemma: If $L$ is regular then $\exists p\ge 1$ such that $\forall w\in L$ with $|w|\ge p$, $\exists$ a split $w=xyz$ with (i) $|xy|\le p$, (ii) $|y|\ge 1$, (iii) $\forall i\ge 0,\ xy^iz\in L$. (1 mark per quantifier condition set: existence of $p$; the three conditions; universal over $i$.)

(b) (7)

• Assume $L$ regular; let $p$ be the pumping length. (1)
• Choose $w=a^p b^p\in L$, $|w|=2p\ge p$. (2)
• By the lemma $w=xyz$ with $|xy|\le p$ and $|y|\ge1$. Since $|xy|\le p$, both $x,y$ lie in the first $p$ symbols, all $a$'s; so $y=a^k$ with $k\ge1$. (2)
• Pump $i=2$: $xy^2z=a^{p+k}b^p$. Since $k\ge1$, $p+k\ne p$, so this string $\notin L$. (2)
• Contradiction with (iii); hence $L$ is not regular. $\blacksquare$

Q3 (12)

(a) (3) Leftmost derivation of $abab$: $S\Rightarrow SS \Rightarrow aSbS \Rightarrow abS \Rightarrow abaSb \Rightarrow abab$ (using $S\to SS$, then first $S\to aSb$, inner $S\to\varepsilon$, second $S\to aSb$, inner $S\to\varepsilon$). Parse tree (bracketed): S[ S[a S[ε] b] S[a S[ε] b] ]. (1 for valid derivation, 1 for leftmost order, 1 for tree.)

(b) (9) Step 1 — remove $\varepsilon$: $S$ is nullable. Removing $\varepsilon$ from RHS:

• $S\to aSb$ gives $aSb$ and $ab$.
• $S\to SS$ gives $SS$, $S$ (either factor nullable). Nullable-removed set (add new start $S_0\to S\mid\varepsilon$ to keep $\varepsilon$ since $\varepsilon\in L$): $S_0\to S\mid\varepsilon$; $S\to aSb\mid ab\mid SS\mid S$. (3)

Step 2 — remove unit productions: Units: $S_0\to S$, $S\to S$. Drop $S\to S$. Replace $S_0\to S$ by $S$'s rules: $S_0\to aSb\mid ab\mid SS\mid \varepsilon$; $S\to aSb\mid ab\mid SS$. (3)

Step 3 — CNF: Introduce terminals $A\to a$, $B\to b$. Then $ab\to AB$, and $aSb$: introduce $C\to SB$, so $aSb\to AC$. Final CNF: $S_0\to AC\mid AB\mid SS\mid \varepsilon,\quad S\to AC\mid AB\mid SS$ $C\to SB,\quad A\to a,\quad B\to b$ (The lone $\varepsilon$ on the start symbol is permitted in CNF because $\varepsilon\in L$ and $S_0$ never appears on a RHS.) (3)

Q4 (10)

(a) (7) PDA $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,\varnothing)$ accepting by empty stack:

• $Q=\{q_0,q_1\}$, $\Sigma=\{a,b\}$, $\Gamma=\{A,Z_0\}$, start state $q_0$, start stack $Z_0$.
• $\delta(q_0,a,Z_0)=\{(q_0,AZ_0)\}$ — push first $a$.
• $\delta(q_0,a,A)=\{(q_0,AA)\}$ — push each further $a$.
• $\delta(q_0,b,A)=\{(q_1,\varepsilon)\}$ — first $b$ pops an $A$, switch to matching mode.
• $\delta(q_1,b,A)=\{(q_1,\varepsilon)\}$ — each subsequent $b$ pops an $A$.
• $\delta(q_1,\varepsilon,Z_0)=\{(q_1,\varepsilon)\}$ — pop the bottom marker to empty stack (accept). (1 per correct transition, 2 for correct tuple/setup.)

(b) (3) Configurations on $aabb$ (state, remaining input, stack): $(q_0,aabb,Z_0)\vdash(q_0,abb,AZ_0)\vdash(q_0,bb,AAZ_0)\vdash(q_1,b,AZ_0)\vdash(q_1,\varepsilon,Z_0)\vdash(q_1,\varepsilon,\varepsilon)$. Stack empty, input consumed ⇒ accept.

Q5 (10)

(a) (3) $A_{TM}=\{\langle M,w\rangle : M \text{ is a TM that accepts } w\}$.

• Decidable (recursive): some TM halts on every input and decides membership (accepts strings in the language, rejects those not).
• Recognizable (r.e.): some TM accepts exactly the strings in the language, but may loop on non-members. (1 for definition, 1 each for decidable/recognizable distinction.)

(b) (7)

• Suppose $HALT_{TM}$ (or $A_{TM}$) is decidable by a decider $H$: $H(\langle M,w\rangle)$ accepts iff $M$ accepts $w$, and always halts. (2)
• Construct $D$: on input $\langle M\rangle$, run $H(\langle M,\langle M\rangle\rangle)$; if $H$ accepts (i.e. $M$ accepts $\langle M\rangle$) then $D$ rejects; if $H$ rejects then $D$ accepts. (2)
• $D$ is a TM, so consider $D(\langle D\rangle)$: (1)
  • If $D$ accepts $\langle D\rangle$, then by construction $H$ said $D$ does not accept $\langle D\rangle$ — contradiction.
  • If $D$ rejects $\langle D\rangle$, then $H$ said $D$ does accept $\langle D\rangle$ — contradiction. (1)
• Either way contradiction ⇒ no such $H$ exists ⇒ the problem is undecidable. $\blacksquare$ (1)

Q6 (8)

(a) (2) $L$ is NP-complete iff (i) $L\in$ NP, and (ii) $L$ is NP-hard: every $L'\in$ NP reduces to $L$ in polynomial time ($\le_p$). (1 each.)

(b) (6) Reduction 3-SAT $\le_p$ CLIQUE. Given a 3-CNF formula $\phi$ with $m$ clauses $C_1,\dots,C_m$, each $C_i=(\ell_{i1}\lor\ell_{i2}\lor\ell_{i3})$:

• Vertices: one node per literal occurrence: $\{(i,j)\}$, total $3m$. (1)
• Edges: connect $(i,j)$–$(i',j')$ iff $i\ne i'$ (different clauses) and the literals are not contradictory ($\ell_{ij}\ne\neg\ell_{i'j'}$). (2)
• Target: $k=m$. Construction is polynomial. (1)
• Correctness: A satisfying assignment picks at least one true literal per clause; those $m$ chosen literals are in distinct clauses and mutually consistent (no literal and its negation both true), so they are pairwise adjacent ⇒ an $m$-clique. Conversely an $m$-clique must use one vertex from each of the $m$ clauses (edges never join same-clause nodes) and contains no contradictory pair, so setting those literals true is a consistent satisfying assignment. (2)

[
  {"claim":"Q1 subset construction yields exactly 3 reachable DFA states",
   "code":"start=frozenset({'q0'}); delta={('q0','a'):{'q0','q1'},('q0','b'):{'q0'},('q1','b'):{'q2'}}\ndef move(S,c):\n    r=set()\n    for s in S: r|=delta.get((s,c),set())\n    return frozenset(r)\nseen={start}; stack=[start]\nwhile stack:\n    S=stack.pop()\n    for c in 'ab':\n        T=move(S,c)\n        if T not in seen: seen.add(T); stack.append(T)\nresult=(len(seen)==3)"},
  {"claim":"Q2 pumping: for w=a^p b^p with y=a^k (k>=1), pumping i=2 leaves unequal counts",
   "code":"p=5; k=2; a_count=p+k; b_count=p; result=(a_count!=b_count)"},
  {"claim":"Q4 PDA trace on aabb ends with empty stack and empty input",
   "code":"config=('q0','aabb',['Z0'])\nsteps=[('q0','abb',['A','Z0']),('q0','bb',['A','A','Z0']),('q1','b',['A','Z0']),('q1','',['Z0']),('q1','',[])]\nfinal=steps[-1]; result=(final[1]=='' and final[2]==[])"},
  {"claim":"Q6 3-SAT to CLIQUE: number of vertices is 3m and clique target is m",
   "code":"m=4; vertices=3*m; target=m; result=(vertices==12 and target==4)"}
]