BE Computer Engineering (Pokhara University) Theory of Computation (PU, CMP 264) Question Paper 2079 Nepal

(a) DFA vs NFA (4 marks)

Computational power: DFA and NFA are equivalent — they recognize exactly the same class of languages (the regular languages). Every NFA can be converted to an equivalent DFA by subset construction. NFAs are often more compact (an $n$-state NFA may need up to $2^n$ DFA states), but they accept no language a DFA cannot.

(b) Subset construction of $M$ (8 marks)

NFA: states $\{q_0,q_1,q_2\}$, start $q_0$, accept $q_2$. $\delta(q_0,0)=\{q_0,q_1\}$, $\delta(q_0,1)=\{q_0\}$, $\delta(q_1,1)=\{q_2\}$. (All other moves $=\emptyset$; no $\varepsilon$-moves.)

Start DFA state $=\{q_0\}$. Compute reachable subsets:

• on 0 from $\{q_0,q_1\}$: $\delta(q_0,0)\cup\delta(q_1,0)=\{q_0,q_1\}\cup\emptyset=\{q_0,q_1\}$.
• on 1 from $\{q_0,q_1\}$: $\{q_0\}\cup\{q_2\}=\{q_0,q_2\}$.
• on 1 from $\{q_0,q_2\}$: $\{q_0\}\cup\emptyset=\{q_0\}$.

Renaming: $A=\{q_0\}$ (start), $B=\{q_0,q_1\}$, $C=\{q_0,q_2\}$ (accepting, since it contains $q_2$).

State diagram (described): Start at $A$. $A$ loops on $1$ and goes to $B$ on $0$. $B$ loops on $0$ and goes to $C$ on $1$. $C$ (double circle, accepting) goes to $B$ on $0$ and back to $A$ on $1$.

The DFA accepts exactly those strings containing the substring 01 (the NFA's condition for reaching $q_2$), which matches the original NFA.

(a) CFG definition and ambiguity (6 marks)

A Context-Free Grammar is a 4-tuple $G = (V, T, P, S)$ where:

• $V$ = finite set of variables (non-terminals),
• $T$ = finite set of terminals, $V \cap T = \emptyset$,
• $P$ = finite set of productions of the form $A \to \alpha$ with $A \in V$ and $\alpha \in (V \cup T)^*$,
• $S \in V$ = the start symbol.

Ambiguity: A grammar is ambiguous if some string has two or more distinct parse trees (equivalently, two distinct leftmost derivations).

For $E \to E+E \mid E*E \mid (E) \mid \text{id}$ and the string $\text{id}+\text{id}*\text{id}$:

Parse tree 1 — + applied last (groups as $\text{id}+(\text{id}*\text{id})$):

        E
      / | \
     E  +  E
     |    /|\
    id   E * E
         |   |
        id  id

Parse tree 2 — * applied last (groups as $(\text{id}+\text{id})*\text{id}$):

        E
      / | \
     E  *  E
   / |\    |
  E + E   id
  |   |
 id  id

Two different parse trees for the same string $\Rightarrow$ the grammar is ambiguous.

(b) PDA for $L=\{a^n b^n \mid n\ge 1\}$ by final state (6 marks)

PDA $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ with $Q=\{q_0,q_1,q_2\}$, $\Sigma=\{a,b\}$, $\Gamma=\{Z_0,A\}$, start $q_0$, $F=\{q_2\}$. Idea: push one $A$ per $a$, pop one $A$ per $b$; accept when stack returns to $Z_0$ after at least one matched pair.

Transitions (form $\delta(\text{state},\text{input},\text{top})=(\text{state},\text{push})$):

1. $\delta(q_0,a,Z_0)=(q_0,AZ_0)$ — first $a$.
2. $\delta(q_0,a,A)=(q_0,AA)$ — subsequent $a$'s.
3. $\delta(q_0,b,A)=(q_1,\varepsilon)$ — first $b$, start matching.
4. $\delta(q_1,b,A)=(q_1,\varepsilon)$ — match remaining $b$'s.
5. $\delta(q_1,\varepsilon,Z_0)=(q_2,Z_0)$ — stack empty (of $A$'s) $\Rightarrow$ accept.

Trace on aabb (config = (state, remaining input, stack), top on left):

Input consumed and PDA is in final state $q_2$ $\Rightarrow$ aabb is accepted.

(a) Turing Machine for equal $a$'s and $b$'s (8 marks)

Idea: Repeatedly scan the tape, mark one unmatched $a$ (as $X$) and one unmatched $b$ (as $Y$) per pass, crossing them off. If the tape becomes all $X$/$Y$/blank (no unmatched $a$ or $b$ remains), accept. The empty string is accepted.

States: $q_0$ (find an $a$), $q_1$ (move right seeking a $b$), $q_2$ (move left to start), $q_{acc}$, $q_{rej}$. Symbols $a,b,X,Y,\sqcup$ ($X,Y$ = crossed-out $a,b$).

Working: $q_0$ marks the leftmost unmatched $a$ as $X$ then in $q_1$ searches right for a $b$ to mark as $Y$; or if it first meets a $b$ it marks it $Y$ and in $q_3$ searches for a matching $a$. $q_2$ rewinds to the left end and re-enters $q_0$. When $q_0$ scans the whole tape and reaches $\sqcup$ with no unmatched $a$ or $b$, it accepts.

Run on abba:

1. $q_0$ at a $\to$ write $X$, go $q_1$ right: Xbba.
2. $q_1$ meets first b $\to$ write $Y$, go $q_2$ left: XYba.
3. $q_2$ rewinds to left end, re-enters $q_0$.
4. $q_0$ skips $X,Y$, meets b $\to$ write $Y$, go $q_3$ right: XYYa.
5. $q_3$ meets a $\to$ write $X$, go $q_2$ left: XYYX.
6. $q_2$ rewinds, $q_0$ scans XYYX then $\sqcup$: no unmatched symbol $\Rightarrow$ accept. (abba has 2 $a$'s and 2 $b$'s.)

(b) Halting Problem and undecidability (4 marks)

Halting Problem: Given the description $\langle M\rangle$ of a Turing machine $M$ and an input $w$, decide whether $M$ halts on $w$. Formally $HALT=\{\langle M,w\rangle \mid M \text{ halts on } w\}$.

Proof of undecidability (diagonalization): Suppose a TM $H$ decides $HALT$: $H(\langle M,w\rangle)$ accepts if $M$ halts on $w$, rejects otherwise. Build a TM $D$ that, on input $\langle M\rangle$:

• runs $H(\langle M,\langle M\rangle\rangle)$;
• if $H$ says "halts," then $D$ loops forever;
• if $H$ says "does not halt," then $D$ halts.

Now run $D$ on its own description $\langle D\rangle$:

• If $D$ halts on $\langle D\rangle$, then $H$ reported "halts," so $D$ loops — contradiction.
• If $D$ does not halt on $\langle D\rangle$, then $H$ reported "does not halt," so $D$ halts — contradiction.

Both cases are contradictory, so $H$ cannot exist. Therefore the Halting Problem is undecidable. $\blacksquare$

(a) Regular-expression rules + construction (5 marks)

Inductive rules for regular expressions over alphabet $\Sigma$:

1. $\emptyset$ is a RE (denotes $\{\}$), $\varepsilon$ is a RE (denotes $\{\varepsilon\}$), and each $a\in\Sigma$ is a RE (denotes $\{a\}$). (Basis)
2. If $r$ and $s$ are REs, then so are: union $r\mid s$, concatenation $rs$, Kleene star $r^*$, and parenthesization $(r)$. (Induction)
3. Nothing else is a RE. Precedence: $* > \text{concatenation} > \mid$.

Required language: all strings over $\{0,1\}$ that contain at least two consecutive $0$'s (substring 00) and end with 1.

$$r = (0\mid 1)^*\,00\,(0\mid 1)^*\,1$$

This forces an occurrence of 00 somewhere, allows any symbols around it, and ends in 1. (Equivalent forms are acceptable.)

(b) Pumping Lemma and non-regularity of $L=\{a^n b^n\mid n\ge0\}$ (7 marks)

Pumping Lemma (regular languages): If $L$ is regular, there exists a constant $p\ge1$ (the pumping length) such that every string $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with:

1. $|y|\ge1$,
2. $|xy|\le p$,
3. $xy^iz\in L$ for all $i\ge0$.

Proof that $L=\{a^n b^n\}$ is not regular (by contradiction):

Assume $L$ is regular with pumping length $p$. Choose $w=a^p b^p \in L$, $|w|=2p\ge p$. By the lemma, $w=xyz$ with $|xy|\le p$ and $|y|\ge1$.

Since $|xy|\le p$, the first $p$ symbols of $w$ are all $a$'s, so $x$ and $y$ consist only of $a$'s. Write $y=a^k$ with $1\le k\le p$.

Pump with $i=2$: $xy^2z = a^{p+k}\,b^{p}$. This has $p+k$ $a$'s but only $p$ $b$'s, and since $k\ge1$ the counts differ, so $xy^2z \notin L$.

This contradicts condition (3) of the pumping lemma. Hence $L=\{a^n b^n\mid n\ge0\}$ is not regular. $\blacksquare$

DFA for binary numbers divisible by 3 (MSB first)

Idea: Track the value of the prefix read so far modulo 3. Reading a bit $b$ updates the running value $v$ to $2v+b$, so the residue updates as $r \to (2r+b)\bmod 3$. Three states represent the three possible remainders.

States: $q_0$ (remainder 0, start and accepting), $q_1$ (remainder 1), $q_2$ (remainder 2).

Transition table (using $2r+b\bmod 3$):

Derivations: from $q_1$ on 0: $(2\cdot1+0)\bmod3=2\to q_2$; on 1: $(2\cdot1+1)\bmod3=0\to q_0$. From $q_2$ on 0: $(4)\bmod3=1\to q_1$; on 1: $(5)\bmod3=2\to q_2$. From $q_0$ on 0: $0\to q_0$; on 1: $1\to q_1$.

State diagram (described): Three states $q_0,q_1,q_2$. $q_0$ is start and double-circled (accept). Edges as in the table. The empty string and 0 map to $q_0$ (value 0, divisible by 3); e.g. 110 (=6) traces $q_0\to q_1\to q_0\to q_0$, ending accepting.

Justification of states: Each state is the equivalence class of all prefixes whose value $\equiv$ that remainder mod 3; only the remainder matters for future divisibility, so exactly 3 states suffice, and acceptance is exactly remainder 0.

Thompson's construction for $(a\mid b)^* ab$

Thompson's construction builds an $\varepsilon$-NFA inductively, one operator at a time; each sub-NFA has exactly one start and one accept state.

Step 1 — atoms $a$ and $b$:

• $N(a)$: $s_1 \xrightarrow{a} f_1$.
• $N(b)$: $s_2 \xrightarrow{b} f_2$.

Step 2 — union $a\mid b$: add new start $s_3$ and accept $f_3$:

• $s_3 \xrightarrow{\varepsilon} s_1$, $s_3 \xrightarrow{\varepsilon} s_2$ (choose a branch),
• $f_1 \xrightarrow{\varepsilon} f_3$, $f_2 \xrightarrow{\varepsilon} f_3$ (rejoin).

Step 3 — Kleene star $(a\mid b)^*$: add new start $s_4$ and accept $f_4$:

• $s_4 \xrightarrow{\varepsilon} s_3$ (enter loop body once),
• $s_4 \xrightarrow{\varepsilon} f_4$ (skip — accept empty),
• $f_3 \xrightarrow{\varepsilon} s_3$ (repeat),
• $f_3 \xrightarrow{\varepsilon} f_4$ (exit).

Step 4 — concatenation with $a$ then $b$:

• Atom $N(a')$: $s_5 \xrightarrow{a} f_5$; atom $N(b')$: $s_6 \xrightarrow{b} f_6$.
• Concatenate the star NFA, then $a$, then $b$ by linking accept-to-start with $\varepsilon$ (or by merging):
  • $f_4 \xrightarrow{\varepsilon} s_5$,
  • $f_5 \xrightarrow{\varepsilon} s_6$.

Final $\varepsilon$-NFA: start state $= s_4$, single accept state $= f_6$.

             ε        ε  a  ε
 s4 ---ε---> s3 region (a|b)* ---ε---> f4 ---ε---> s5 --a--> f5 ---ε---> s6 --b--> f6 (accept)
  \
   ---ε--> f4   (skip loop)

Where the $(a\mid b)$ block inside the star is: $s_3\xrightarrow{\varepsilon}\{s_1,s_2\}$, $s_1\xrightarrow{a}f_1$, $s_2\xrightarrow{b}f_2$, $f_1,f_2\xrightarrow{\varepsilon}f_3$, with the star back-edge $f_3\xrightarrow{\varepsilon}s_3$ and exit $f_3\xrightarrow{\varepsilon}f_4$.

The resulting NFA accepts any number of $a$/$b$ symbols (the star) followed by the literal ab.

Convert to Chomsky Normal Form

Grammar: $S\to ASA\mid aB$, $A\to B\mid S$, $B\to b\mid\varepsilon$.

Step 1 — add new start symbol $S_0$: $S_0\to S$.

Step 2 — remove $\varepsilon$-productions. Nullable: $B$ (from $B\to\varepsilon$), and $A$ (since $A\to B$). Remove $B\to\varepsilon$ and add versions of productions with nullable symbols omitted.

• $S\to ASA$ gives (drop each nullable $A$): $ASA,\ SA,\ AS,\ S$.
• $S\to aB$ gives: $aB,\ a$.
• $A\to B$ stays (but $B$ now non-nullable form); $A\to S$ stays. Remove $A\to\varepsilon$ if introduced — $A$ was nullable only via $B$, so no $A\to\varepsilon$ unit.
• $B\to b$ stays.

Now: $S_0\to S$; $S\to ASA\mid SA\mid AS\mid S\mid aB\mid a$; $A\to B\mid S$; $B\to b$.

Step 3 — remove unit productions. Unit pairs: $S\to S$ (drop, trivial), $S_0\to S$, $A\to B$, $A\to S$.

• $S_0\to S$: $S_0\to ASA\mid SA\mid AS\mid aB\mid a$.
• $A\to B$: $A\to b$. $A\to S$: $A\to ASA\mid SA\mid AS\mid aB\mid a$.
• Drop $S\to S$.

Now: $S_0\to ASA\mid SA\mid AS\mid aB\mid a$ $S\to ASA\mid SA\mid AS\mid aB\mid a$ $A\to b\mid ASA\mid SA\mid AS\mid aB\mid a$ $B\to b$

Step 4 — replace terminals in long bodies. Introduce $T_a\to a$. Replace $a$ in $aB$: $aB\to T_aB$.

Step 5 — break bodies longer than 2. $ASA$ has length 3; introduce $C\to SA$, so $ASA\to A\,C$ where $C\to SA$.

Resulting CNF grammar:

$$\begin{aligned} S_0 &\to AC \mid SA \mid AS \mid T_aB \mid a\\ S &\to AC \mid SA \mid AS \mid T_aB \mid a\\ A &\to AC \mid SA \mid AS \mid T_aB \mid a \mid b\\ B &\to b\\ C &\to SA\\ T_a &\to a \end{aligned}$$

Every production is now of the form $X\to YZ$ (two variables) or $X\to a$ (single terminal), i.e. valid CNF.

Deterministic vs Non-deterministic PDA

So NPDAs are strictly more powerful than DPDAs (unlike finite automata, where NFA = DFA). Every DPDA language is context-free, but not every CFL is a DPDA language.

PDA equivalent to $S\to aSb\mid\varepsilon$

This grammar generates $L=\{a^n b^n\mid n\ge0\}$. Construct a PDA (acceptance by empty stack), $P=(\{q\},\{a,b\},\{Z_0,A\},\delta,q,Z_0)$:

1. $\delta(q,a,Z_0)=(q,AZ_0)$ — push $A$ on first $a$.
2. $\delta(q,a,A)=(q,AA)$ — push $A$ for each further $a$.
3. $\delta(q,b,A)=(q,\varepsilon)$ — pop one $A$ per $b$.
4. $\delta(q,\varepsilon,Z_0)=(q,\varepsilon)$ — empty stack to accept (handles $n=0$ and the matched case).

Trace aabb: $(q,aabb,Z_0)\vdash(q,abb,AZ_0)\vdash(q,bb,AAZ_0)\vdash(q,b,AZ_0)\vdash(q,\varepsilon,Z_0)\vdash(q,\varepsilon,\varepsilon)$ — accepted. The empty string is accepted directly by rule 4.

Why no finite automaton accepts $L$

$L=\{a^n b^n\}$ requires counting an unbounded number of $a$'s to match the same number of $b$'s. A finite automaton has only finitely many states and no memory (no stack), so it cannot distinguish among the infinitely many prefixes $a^n$. By the pumping lemma for regular languages, pumping $a^p b^p$ unbalances the counts, proving $L$ is not regular. The PDA's stack supplies exactly the unbounded counting memory an FA lacks.

(a) Standard Turing Machine as a 7-tuple (3 marks)

A (deterministic, single-tape) Turing Machine is $M=(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})$ where:

• $Q$ = finite set of states;
• $\Sigma$ = input alphabet, with blank $\sqcup\notin\Sigma$;
• $\Gamma$ = tape alphabet, $\Sigma\subseteq\Gamma$ and $\sqcup\in\Gamma$;
• $\delta : Q\times\Gamma \to Q\times\Gamma\times\{L,R\}$ = transition function (read symbol, write symbol, move head Left/Right);
• $q_0\in Q$ = start state;
• $q_{accept}\in Q$ = accept state;
• $q_{reject}\in Q$ = reject state ($q_{accept}\neq q_{reject}$).

(b) Multi-tape Turing Machine (3 marks)

A multi-tape TM has $k\ge2$ tapes, each with its own independent read/write head. Its transition function reads the $k$ symbols under the heads at once and writes $k$ symbols, moving each head independently:

$$\delta : Q\times\Gamma^k \to Q\times\Gamma^k\times\{L,R,S\}^k.$$

The input starts on tape 1; the other tapes start blank and serve as scratch memory.

Is it more powerful? No — it is equally powerful in terms of the languages it recognizes. Every multi-tape TM can be simulated by a single-tape TM (store the $k$ tapes' contents interleaved on one tape, marking head positions, and sweep the tape to simulate each step). Both models recognize exactly the recursively enumerable languages, confirming the Church–Turing thesis. The only difference is efficiency: a $t$-step multi-tape computation costs $O(t^2)$ steps on a single tape, so multi-tape gives a polynomial speedup but no extra computational power.

Recursive vs Recursively Enumerable languages

Recursive (decidable) language: A language $L$ is recursive if there is a Turing machine that halts on every input and decides membership — it accepts every $w\in L$ and rejects (halts) every $w\notin L$. The machine is a total decider.

Recursively enumerable (RE / Turing-recognizable): $L$ is RE if there is a TM that accepts every $w\in L$, but on $w\notin L$ it may reject or run forever (it need not halt). The machine is a recognizer, not necessarily a decider.

Examples:

• Recursive: $\{a^n b^n c^n\}$, or any CFL, or $\{\langle M\rangle \mid M$ has $\le 5$ states$\}$ — membership is always decidable.
• RE but not recursive: $A_{TM}=\{\langle M,w\rangle \mid M$ accepts $w\}$ (the acceptance/halting problem) — recognizable by a universal TM that simulates $M$ on $w$, but undecidable.

Relationship via closure under complement

• Every recursive language is RE (a decider is also a recognizer): $\text{Recursive}\subseteq\text{RE}$.
• Recursive languages are closed under complement: if $M$ decides $L$, swap its accept/reject states to decide $\overline{L}$ (it still always halts).
• Key theorem: $L$ is recursive iff both $L$ and $\overline{L}$ are RE. Run recognizers for $L$ and $\overline{L}$ in parallel; on any input exactly one accepts, giving a decider that always halts.
• RE is not closed under complement. Since $A_{TM}$ is RE but undecidable, its complement $\overline{A_{TM}}$ cannot be RE — otherwise $A_{TM}$ would be recursive. Thus $\text{Recursive}\subsetneq\text{RE}$, and $\overline{A_{TM}}$ is an example of a language that is not even RE.

(a) P, NP, and NP-completeness (4 marks)

• $P$ (Polynomial time): the class of decision problems solvable by a deterministic Turing machine in time $O(n^k)$ for some constant $k$, where $n$ is the input size. These are the problems regarded as efficiently solvable.
• $NP$ (Non-deterministic Polynomial time): the class of decision problems for which a proposed solution (certificate) can be verified by a deterministic TM in polynomial time; equivalently, solvable by a non-deterministic TM in polynomial time. Clearly $P\subseteq NP$.
• $NP$-complete: a problem $X$ is NP-complete if (1) $X\in NP$, and (2) every problem in $NP$ reduces to $X$ in polynomial time ($X$ is NP-hard). NP-complete problems are the "hardest" in $NP$: if any one of them is in $P$, then $P=NP$.

(b) Significance of P vs NP, and an example (3 marks)

Significance: The $P\overset{?}{=}NP$ question asks whether every problem whose solution can be verified quickly can also be solved quickly. It is one of the seven Millennium Prize Problems. If $P=NP$, thousands of important optimization, scheduling, and cryptographic-breaking problems would have efficient algorithms; if $P\neq NP$ (widely believed), no polynomial-time algorithm exists for NP-complete problems, which underpins the security of modern cryptography. It remains open.

Example of an NP-complete problem: The Boolean Satisfiability problem (SAT) — deciding whether a Boolean formula has a satisfying assignment — was the first proven NP-complete problem (Cook–Levin theorem). Other examples: the Travelling Salesman (decision) problem, 3-SAT, Vertex Cover, Hamiltonian Cycle, and Subset Sum.

Proof by induction: number of strings of length $n$ over $|\Sigma|=k$ is $k^n$

Let $P(n)$ be the statement: the number of distinct strings of length $n$ over an alphabet $\Sigma$ with $|\Sigma|=k$ equals $k^n$.

Basis ($n=1$): A string of length 1 is just a single symbol from $\Sigma$. There are exactly $|\Sigma|=k$ choices, and $k^1=k$. So $P(1)$ holds.

(Optional stronger basis $n=0$: there is exactly one string of length 0, the empty string $\varepsilon$, and $k^0=1$, so it also holds.)

Inductive hypothesis: Assume $P(n)$ is true for some integer $n\ge1$, i.e. there are exactly $k^n$ distinct strings of length $n$.

Inductive step — show $P(n+1)$: Every string of length $n+1$ is obtained uniquely by taking a string $w$ of length $n$ and appending one symbol $a\in\Sigma$ to its end, giving $wa$.

• By the inductive hypothesis there are $k^n$ choices for $w$.
• There are $k$ choices for the appended symbol $a$.
• Different $(w,a)$ pairs produce different strings, and every length-$(n+1)$ string arises from exactly one such pair.

By the multiplication (product) rule, the number of strings of length $n+1$ is

$$k^n \cdot k = k^{n+1}.$$

Thus $P(n+1)$ holds.

Conclusion: By the principle of mathematical induction, $P(n)$ holds for every integer $n\ge1$: the number of distinct strings of length $n$ over an alphabet of size $k$ is exactly $k^n$. $\blacksquare$