Theory of Computation

Q1. (4 marks)

• (a) An alphabet $\Sigma$ is a finite, non-empty set of symbols. (1)
• (b) A string (word) over $\Sigma$ is a finite sequence of symbols from $\Sigma$. (1)
• (c) A language over $\Sigma$ is any set of strings, i.e. a subset $L \subseteq \Sigma^*$. (1)
• Empty string $\varepsilon$ = string of length $0$; $\Sigma^* = \bigcup_{k\ge 0}\Sigma^k$ is the set of all finite strings over $\Sigma$ (including $\varepsilon$). (1)

Why: these are the foundational objects; a language is a set of strings so machines/grammars can "decide/generate" it.

Q2. (4 marks) A DFA is $M=(Q,\Sigma,\delta,q_0,F)$: (1 for tuple)

• $Q$: finite set of states; (½)
• $\Sigma$: input alphabet; (½)
• $\delta:Q\times\Sigma\to Q$: transition function (total, single next state); (1)
• $q_0\in Q$: start state; (½)
• $F\subseteq Q$: set of accepting states. (½)

Why: determinism = exactly one transition per (state, symbol) pair; a string is accepted iff $\delta^*(q_0,w)\in F$.

Q3. (4 marks) States $\{q_0,q_1,q_2\}$, start $q_0$, accept $\{q_2\}$. (1) Transitions: (2)

• $q_0$: on $0\to q_1$, on $1\to q_0$
• $q_1$: on $0\to q_1$, on $1\to q_2$
• $q_2$: on $0\to q_1$, on $1\to q_0$

$q_2$ = "just saw $01$"; $q_1$ = "just saw $0$". (1 for correct accept condition)

Why: the machine tracks the longest suffix so far matching a prefix of "01"; only reaching $q_2$ (ending in $01$) accepts.

Q4. (5 marks) Subsets reachable from $\{q_0\}$:

• $\{q_0\}$ on $a\to \{q_0,q_1\}$ (1)
• $\{q_0,q_1\}$ on $a\to \delta(q_0,a)\cup\delta(q_1,a)=\{q_0,q_1\}\cup\varnothing=\{q_0,q_1\}$ (1)

DFA: states $\{q_0\}$ (start), $\{q_0,q_1\}$ (accepting, since contains $q_1$). (2)

• $\{q_0\}\xrightarrow{a}\{q_0,q_1\}\xrightarrow{a}\{q_0,q_1\}$.

Accepted language: $\{a^n : n\ge 1\} = a a^*$ — all non-empty strings of $a$'s. (1)

Why: subset construction tracks the set of NFA states; a DFA state is accepting iff it contains an NFA accepting state. $\varepsilon$ is rejected because start subset $\{q_0\}$ has no accept state.

Q5. (3 marks)

• (a) $(a+b)^* a (a+b)^*$ (1)
• (b) $((a+b)(a+b))^*$ (1)
• (c) $a(a+b)^* b$ (1)

Why: (a) force at least one $a$; (b) length multiple of 2 via pairs; (c) fix first and last symbols.

Q6. (5 marks) Pumping Lemma: If $L$ is regular, there exists $p\ge 1$ (pumping length) such that every $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with (i) $|y|\ge 1$, (ii) $|xy|\le p$, (iii) $xy^iz\in L$ for all $i\ge 0$. (2)

Proof of non-regularity of $L=\{a^nb^n\}$: Assume regular with pumping length $p$. Take $w=a^p b^p\in L$, $|w|=2p\ge p$. (1) By (ii), $xy$ lies within the first $p$ symbols, all $a$'s, so $y=a^k$ with $k\ge 1$. (1) Pump $i=2$: $xy^2z=a^{p+k}b^p$ with $p+k\ne p$, so it has more $a$'s than $b$'s $\Rightarrow xy^2z\notin L$, contradicting (iii). Hence $L$ is not regular. (1)

Why: the constraint $|xy|\le p$ forces the pumped part into the $a$-block, breaking the equal-count condition.

Q7. (4 marks) Grammar: $S\to aSb \mid \varepsilon$. (2) Leftmost derivation of $aabb$: (2) $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aa\varepsilon bb = aabb.$

Why: each application adds one matching $a\dots b$ pair; termination via $S\to\varepsilon$ guarantees equal counts.

Q8. (3 marks) (a) Every production is of the form: (2, ~⅔ each)

• $A\to BC$ (two non-terminals), or
• $A\to a$ (single terminal), and
• optionally $S\to\varepsilon$ (only start symbol may derive $\varepsilon$), with $S$ not on any RHS.

(b) Useful reason (any one): CNF gives parse trees that are binary, enabling the CYK parsing algorithm ($O(n^3)$ membership testing) and simplifying inductive proofs. (1)

Q9. (4 marks)

• P: the class of languages decidable by a deterministic Turing machine in time $O(n^k)$ for some constant $k$ (polynomial time). (1.5)
• NP: the class of languages $L$ for which there is a polynomial-time verifier $V$ and polynomial $p$ such that $x\in L \iff \exists c,\ |c|\le p(|x|),\ V(x,c)$ accepts. ($c$ = certificate/witness.) (1.5)
• P vs NP: Is $P = NP$? I.e., can every problem whose solutions are efficiently verifiable also be efficiently solved? (1)

Why: NP captures "easy to check", P captures "easy to solve"; equality is an open Millennium problem.

Q10. (4 marks) (a) Halting Problem: given a Turing machine $M$ and input $w$, does $M$ halt on $w$? The language $A_{TM}^{halt}=\{\langle M,w\rangle : M \text{ halts on } w\}$ is undecidable (recognizable but not recursive), proved by diagonalization. (2) (b) Rice's theorem: every non-trivial semantic property of the language recognized by a Turing machine is undecidable. (2)

Why: diagonalization derives a contradiction from a supposed decider; Rice generalizes undecidability to all non-trivial properties of r.e. languages.

[
  {"claim":"Subset construction of NFA yields only states {q0} and {q0,q1}; language is a a*",
   "code":"from sympy import symbols\n# simulate NFA on a-strings, check accepted set = {n>=1}\ndef nfa_accepts(n):\n    # states reachable after n a's\n    states={'q0'}\n    for _ in range(n):\n        nxt=set()\n        for s in states:\n            if s=='q0': nxt|={'q0','q1'}\n        states=nxt\n    return 'q1' in states\naccepted=[n for n in range(6) if nfa_accepts(n)]\nresult = accepted==[1,2,3,4,5]"},
  {"claim":"Pumping a^p b^p with y=a^k (k>=1), i=2 breaks equality: count a != count b",
   "code":"p=5; k=2\nw_a=p+k; w_b=p\nresult = (w_a != w_b) and (w_a==p+k) and (w_b==p)"},
  {"claim":"CFG S->aSb|eps derives aabb via two aSb applications then eps",
   "code":"steps=['S','aSb','aaSbb','aabb']\nfinal=steps[-1]\nresult = final=='aabb' and final.count('a')==final.count('b')==2"},
  {"claim":"Regex ((a+b)(a+b))* matches exactly even-length strings",
   "code":"import re\npat=re.compile('^((a|b)(a|b))*$')\nstrings=['','a','ab','aba','abab','b']\nres={s:bool(pat.match(s)) for s in strings}\nexpected={'':True,'a':False,'ab':True,'aba':False,'abab':True,'b':False}\nresult = res==expected"}
]