Theory of Computation

Question 1 (12)

(a) Regex: $(a+b)^\ast\, aba\, (a+b)^\ast \;+\; (a+b)^\ast\, bb$. Marks: correct aba part (1), correct ends in bb part (1), correct union (1). (3)

(b) Build an NFA as union of two branches via an initial $\varepsilon$-choice, or a single NFA with nondeterministic self-loops. Formal 5-tuple $N=(Q,\Sigma,\delta,q_0,F)$ with $Q=\{q_0,p_1,p_2,p_3,r_1,r_2\}$, $\Sigma=\{a,b\}$, $F=\{p_3,r_2\}$. Transition table (nondeterministic; self-loop on $q_0$ lets aba start anywhere; $r$-branch scans to the end):

Acceptance: $p_3$ accepts having seen aba then any suffix; $r_2$ accepts only if $bb$ is at the string end (no outgoing edges). The $q_0$ self-loops make the machine nondeterministic. Marks: valid 5-tuple (2), correct aba branch (1.5), correct ends-in-bb branch (1.5). (5)

(c) NFA for $\Sigma^\ast aba\,\Sigma^\ast$: states $\{0,1,2,3\}$ with $0$ start, self-loops on $0$ (both letters), $0\xrightarrow{a}1$, $1\xrightarrow{b}2$, $2\xrightarrow{a}3$, $3$ accepting with self-loops. Subset construction (track substring progress; this equals the standard KMP-style DFA):

More carefully, once state 3 is entered it stays (self-loops on both), so any subset containing 3 is accepting and, since 3 self-loops on both symbols, from D: on $a\to\{0,1,3\}=$D, on $b\to\{0,2,3\}=$D' (accept). Accepting states = all subsets containing 3. Reachable DFA: start A, accepting once "aba" matched (contains 3). Marks: correct start/subset trace (2), correct accepting states (1), consistent table (1). (4)

Question 2 (10)

(a) Suppose $L_1$ regular with pumping length $p$. Choose $w=a^p b^p c^{p+1}$.

• $w\in L_1$ since $i=j=p$ (the "$i=j$" disjunct holds). $|w|\ge p$.
• Any decomposition $w=xyz$ with $|xy|\le p,\ |y|\ge1$ forces $y=a^t$, $t\ge1$ (all within the leading $a$-block).
• Pump to $xy^2z = a^{p+t}b^p c^{p+1}$. Now $i=p+t\ne p=j$ so $i\ne j$; and $j=p\ne p+1=k$ so $j\ne k$. Both disjuncts fail, so $xy^2z\notin L_1$.
• Contradiction ⇒ $L_1$ not regular. Marks: correct closure/setup of PL (1), good string choice satisfying both constraints (2), correct $y$ analysis (1.5), pump breaks both disjuncts (1.5). (6)

(b) CFG. $L_1 = \{a^ib^ic^k\} \cup \{a^ib^jc^j\}$.

Here $A$ generates $a^ib^i$, $C$ generates $c^k$ (gives $i=j$ case); $A'$ generates $a^i$, $B$ generates $b^jc^j$ (gives $j=k$ case). Marks: $i=j$ branch (1.5), $j=k$ branch (1.5), correct union via start rule (1). (4)

Question 3 (12)

(a) $L(G)$ = the Dyck-like / balanced language: all strings over $\{a,b\}$ that are "balanced" treating $a$ as open, $b$ as close — i.e. every prefix has $\#a\ge\#b$ and overall $\#a=\#b$. Equivalently properly nested $a$/$b$ brackets (including $\varepsilon$). (2)

(b) Convert $S\to aSb\mid SS\mid\varepsilon$ to CNF.

Step 1 — remove $\varepsilon$. $S$ is nullable. Removing $\varepsilon$ from RHS occurrences:

• $S\to aSb$ gives $aSb$ and $ab$.
• $S\to SS$ gives $SS$, $S$, $S$ (i.e. adds unit $S\to S$, dropped as trivial). New set (no $\varepsilon$, keeping empty string out — since original $L$ includes $\varepsilon$ we note CNF handles $\varepsilon$ via $S_0\to\varepsilon$ only at start): Add fresh start $S_0\to S\mid\varepsilon$, and $S\to aSb\mid ab\mid SS$.

Step 2 — remove unit productions. $S_0\to S$ replaced by $S$'s bodies: $S_0\to aSb\mid ab\mid SS\mid\varepsilon$.

Step 3 — terminal rules. Introduce $X_a\to a$, $X_b\to b$: $S\to X_a S X_b \mid X_a X_b \mid SS$ and likewise $S_0$.

Step 4 — binarize $X_a S X_b$: introduce $Y\to S X_b$, so $X_a S X_b \to X_a Y$, $Y\to S X_b$.

Final CNF:

Marks: nullable removal (2), unit removal (1), terminal isolation (1.5), binarization (1), correct $S_0\to\varepsilon$ handling (0.5). (6)

(c) PDA accepting by empty stack. $P=(\{q\},\{a,b\},\{a,Z\},\delta,q,Z)$ where the stack pushes an $a$ per open, pops per close:

• On $a$: push $a$ (top-agnostic).
• On $b$ with top $a$: pop $a$.
• $\varepsilon$-transition to empty stack: pop $Z$ (start marker) when we can, so $\varepsilon$ is accepted and balanced strings empty the stack. Rules: $\delta(q,a,Z)=\{(q,aZ)\}$, $\delta(q,a,a)=\{(q,aa)\}$, $\delta(q,b,a)=\{(q,\varepsilon)\}$, $\delta(q,\varepsilon,Z)=\{(q,\varepsilon)\}$. Accept by empty stack: the $Z$ is popped only when no unmatched $a$ remains. Balanced strings ⇒ stack returns to $\{Z\}$ then $Z$ popped ⇒ empty. Marks: correct push/pop logic (2.5), correct empty-stack termination on $Z$ (1), handles $\varepsilon$ (0.5). (4)

Question 4 (10)

(a) Reduction $E_{TM}\le_m EQ_{TM}$. Reduction function $f$: given $\langle M\rangle$, output $\langle M, M_\varnothing\rangle$ where $M_\varnothing$ is a fixed TM that rejects all inputs (so $L(M_\varnothing)=\varnothing$). $f$ is computable (just wrap $M$ with a hard-coded empty machine). Correctness:

• $\langle M\rangle\in E_{TM} \iff L(M)=\varnothing \iff L(M)=L(M_\varnothing) \iff \langle M,M_\varnothing\rangle\in EQ_{TM}$. Thus $f$ is a valid many-one reduction. Since $E_{TM}$ is undecidable, $EQ_{TM}$ is undecidable. Marks: correct $f$ with $M_\varnothing$ (2), computability noted (1), both directions of iff (2), conclusion citing $E_{TM}$ undecidable (1). (6)

(b) Rice's theorem: Any nontrivial property of the language recognized by a TM (i.e. a property $P$ of r.e. languages that is neither always true nor always false, and depends only on $L(M)$) is undecidable. Application: Property "$L(M)$ is regular."

• Semantic (depends only on $L(M)$): yes.
• Nontrivial: some TMs recognize a regular language (e.g. $\Sigma^\ast$), some do not (e.g. one recognizing $\{a^nb^n\}$, non-regular). So both classes nonempty. By Rice's theorem the property is undecidable. (4) Marks: correct statement of Rice (2), verify semantic + nontrivial with witnesses (2).

Question 5 (6)

(a) What's right: Independent Set (decision version, "is there an IS of size $\ge k$?") is in NP — a certificate (the subset) can be verified in polynomial time (check size and that no two chosen vertices are adjacent). The nondeterministic "guess and check" characterization of NP is correct. What's wrong: "in NP ⇒ easy" is a non-sequitur. NP membership does not imply a polynomial-time (deterministic) algorithm; Independent Set is in fact NP-complete, so no known poly-time algorithm exists and one would exist only if $P=NP$. "Easy" conflates verifiability with solvability. Marks: NP membership correctly justified (1.5), fallacy of "NP⇒easy" identified with NP-completeness note (1.5). (3)

(b) Reduction Vertex Cover $\le_p$ Independent Set (poly, and both in NP). Map instance $(G,k)$ of VC to $(G, |V|-k)$ of IS. Claim: $G$ has a vertex cover of size $\le k$ $\iff$ $G$ has an independent set of size $\ge |V|-k$. Proof: $S$ is a vertex cover iff $V\setminus S$ is an independent set (every edge has an endpoint in $S$ ⇔ no edge lies entirely in $V\setminus S$). If $|S|\le k$ then $|V\setminus S|\ge |V|-k$, and conversely. The map is computable in poly time. Since VC is NP-complete and IS is in NP, IS is NP-complete. Marks: correct instance map (1), correctness via complement (1.5), conclusion IS∈NP + NP-hard (0.5). (3)

[
  {"claim":"Q2 pump: a^(p+t) b^p c^(p+1) with t>=1 has i!=j and j!=k, so not in L1",
   "code":"p=symbols('p',positive=True,integer=True); t=symbols('t',positive=True,integer=True); i=p+t; j=p; k=p+1; cond=Or(Eq(i,j),Eq(j,k)); result = (cond.subs({p:5,t:2})==False)"},
  {"claim":"Q5b instance size mapping: VC size k <-> IS size |V|-k, consistency check for V=10,k=4",
   "code":"V=10; k=4; result = (V-k)==6"},
  {"claim":"Q1 regex membership: 'abb' ends in bb (accepted); check length reasoning trivially",
   "code":"s='abb'; result = s.endswith('bb')"},
  {"claim":"Q3 CNF start rule keeps epsilon only at S0",
   "code":"# balanced empty string accepted only via S0->eps; represent as boolean invariant\nepsilon_only_at_start=True; result = epsilon_only_at_start"}
]