BE Computer Engineering (IOE, TU) Theory of Computation (IOE, CT 502) Question Paper 2078 Nepal

(a) Formal definition of an NFA

A Non-deterministic Finite Automaton (NFA) is a 5-tuple

$$M = (Q, \Sigma, \delta, q_0, F)$$

where:

• $Q$ — a finite, non-empty set of states.
• $\Sigma$ — a finite input alphabet (the symbols the machine reads).
• $\delta$ — the transition function $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^{Q}$. For a given state and input symbol it returns a set of possible next states (possibly empty), and $\varepsilon$-moves allow changing state without reading input.
• $q_0 \in Q$ — the start (initial) state.
• $F \subseteq Q$ — the set of final (accepting) states.

A string $w$ is accepted if at least one computation path ends in a state of $F$.

NFA vs DFA

Both accept exactly the regular languages — they are equivalent in power.

(b) NFA for strings containing aba, then subset construction

NFA $N$ with states $\{A,B,C,D\}$, start $A$, final $D$:

State $A$ loops on every symbol (still searching); $A\xrightarrow{a}B\xrightarrow{b}C\xrightarrow{a}D$ recognises aba; $D$ is a trap-accept state. (No $\varepsilon$-transitions are actually needed, so $\varepsilon$-closure of each state is the state itself.)

Subset construction

Start subset $= \{A\}$.

Final states are all subsets containing $D$: $S_3, S_4, S_5$.

Resulting DFA (described)

• Start state: $S_0=\{A\}$.
• Accepting states (double circle): $S_3,S_4,S_5$.
• Transitions as in the table. Once any accepting state is reached (substring aba seen) the machine stays among accepting states forever, since every subsequent subset still contains $D$.

This DFA accepts exactly the strings over $\{a,b\}$ that contain the substring aba.

(a) Derivation, parse tree and $L(G)$ for $S \to aSb \mid SS \mid \varepsilon$

Leftmost derivation of aabbab:

$$S \Rightarrow SS \Rightarrow aSbS \Rightarrow aaSbbS \Rightarrow aa\varepsilon bbS \Rightarrow aabbS \Rightarrow aabb\,aSb \Rightarrow aabb\,a\varepsilon b \Rightarrow aabbab$$

So aabbab $= (aabb)(ab)$, two balanced blocks concatenated.

Parse tree (described):

            S
           / \
          S   S
         /|\   /|\
        a S b a S b
          |     |
          S     S
         /|\    |
        a S b   ε
          |
          ε

• Root $S \to S\,S$.
• Left $S \Rightarrow aSb \Rightarrow a(aSb)b \Rightarrow aabb$ (innermost $S\to\varepsilon$).
• Right $S \to aSb \Rightarrow ab$ (with $S\to\varepsilon$).

Language generated:

$$L(G) = \{\, w \in \{a,b\}^* \mid w \text{ is a string of balanced parentheses with } a=\text{`(' and } b=\text{`)'}\,\}$$

i.e. the set of all strings in which every prefix has $\#a \ge \#b$ and the whole string has $\#a = \#b$ — the balanced / Dyck language over $\{a,b\}$.

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

$$M = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$$

with $Q=\{q_0,q_1,q_2\}$, $\Sigma=\{a,b\}$, $\Gamma=\{A,Z_0\}$, start state $q_0$, start stack symbol $Z_0$, $F=\{q_2\}$.

Transition function:

1. $\delta(q_0,a,Z_0) = \{(q_0,AZ_0)\}$ — push first $A$.
2. $\delta(q_0,a,A) = \{(q_0,AA)\}$ — push an $A$ for each $a$.
3. $\delta(q_0,b,A) = \{(q_1,\varepsilon)\}$ — on first $b$, pop one $A$, go to $q_1$.
4. $\delta(q_1,b,A) = \{(q_1,\varepsilon)\}$ — pop one $A$ per $b$.
5. $\delta(q_1,\varepsilon,Z_0) = \{(q_2,Z_0)\}$ — stack back to $Z_0$ (equal $a$'s and $b$'s): accept.

Trace on aaabbb (notation: (state, remaining input, stack), top of stack on the left):

Input consumed and machine in final state $q_2$ ⇒ aaabbb is accepted.

(a) Turing Machine for $L = \{a^n b^n c^n \mid n \ge 1\}$

Idea: repeatedly cross off the leftmost unmarked $a$ (write $X$), then the leftmost $b$ (write $Y$), then the leftmost $c$ (write $Z$); return to the left and repeat until none remain. Accept if everything is matched.

Formal definition $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$:

• $Q=\{q_0,q_1,q_2,q_3,q_4,q_{acc},q_{rej}\}$
• $\Sigma=\{a,b,c\}$
• $\Gamma=\{a,b,c,X,Y,Z,B\}$ ($B$ = blank)
• start $q_0$, $F=\{q_{acc}\}$

Transition function $\delta$ (Right = R, Left = L):

q0 a -> q1, X, R     (mark an a, go find a b)
q0 Y -> q4, Y, R     (no a's left; verify only Y,Z remain)
q1 a -> q1, a, R     (skip a's)
q1 Y -> q1, Y, R     (skip already-marked Y)
q1 b -> q2, Y, R     (mark a b, go find a c)
q2 b -> q2, b, R     (skip b's)
q2 Z -> q2, Z, R     (skip marked Z)
q2 c -> q3, Z, L     (mark a c, turn around)
q3 (a|b|Y|Z) -> q3, same, L   (walk left)
q3 X -> q0, X, R     (back at left boundary, repeat)
q4 Y -> q4, Y, R     (scan remaining Y's)
q4 Z -> q4, Z, R     (scan remaining Z's)
q4 B -> qacc, B, R   (all matched -> accept)

Any missing transition (e.g. seeing $a$ when expecting only $Y,Z$, or a $c$ before a $b$) goes to $q_{rej}$, ensuring strings like $a^2b^2c^3$ or $abcc$ are rejected.

Sequence of configurations (IDs) for input aabbcc (current state shown just left of the scanned symbol):

q0 a a b b c c
X q1 a b b c c
X a q1 b b c c
X a Y q2 b c c
X a Y b q2 c c
X a Y q3 b Z c       (mark c->Z, move L)
X a q3 Y b Z c
X q3 a Y b Z c
q3 X a Y b Z c
X q0 a Y b Z c
X X q1 Y b Z c       (mark a->X)
X X Y q1 b Z c
X X Y Y q2 Z c       (mark b->Y)
X X Y Y Z q2 c
X X Y Y q3 Z Z       (mark c->Z, move L)
X X Y q3 Y Z Z
X X q3 Y Y Z Z
X q3 X Y Y Z Z
X X q0 Y Y Z Z       (no a's left)
X X Y q4 Y Z Z
X X Y Y q4 Z Z
X X Y Y Z q4 Z
X X Y Y Z Z q4 B
X X Y Y Z Z B qacc   -> ACCEPT

(b) The Halting Problem and its undecidability

Statement. Given the encoding $\langle M\rangle$ of an arbitrary Turing machine $M$ and an input $w$, decide whether $M$ halts on $w$. Formally, decide membership in

$$HALT = \{\,\langle M,w\rangle \mid M \text{ halts on input } w\,\}.$$

The Halting Problem asks for an algorithm (a TM $H$ that always halts) deciding $HALT$.

Proof of undecidability (diagonalization / contradiction).

Assume, for contradiction, that a TM $H$ decides $HALT$:

$$H(\langle M\rangle, w) = \begin{cases} \text{accept} & \text{if } M \text{ halts on } w \\ \text{reject} & \text{if } M \text{ loops on } w \end{cases}$$

Construct a TM $D$ that takes a single input $\langle M\rangle$ and runs $H(\langle M\rangle,\langle M\rangle)$:

• If $H$ says "$M$ halts on $\langle M\rangle$", then $D$ loops forever.
• If $H$ says "$M$ loops on $\langle M\rangle$", then $D$ halts.

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

• If $D$ halts on $\langle D\rangle$, then by construction $H$ said it loops, so $D$ must loop — contradiction.
• If $D$ loops on $\langle D\rangle$, then $H$ said it halts, so $D$ must halt — contradiction.

Either way we reach a contradiction, so the assumed decider $H$ cannot exist. Hence the Halting Problem is undecidable. $\blacksquare$

Significance.

• It is the first concrete, natural problem proven algorithmically unsolvable, establishing a hard limit on what computers can do.
• It shows the class of recursively enumerable languages strictly contains the recursive (decidable) languages ($HALT$ is r.e. but not recursive).
• Via reduction, undecidability of $HALT$ propagates to many practical problems (program verification, equivalence of programs, Rice's theorem properties), proving no general algorithm can decide them.

The Chomsky Hierarchy of Grammars

Proposed by Noam Chomsky (1956), it classifies grammars (and the languages/automata they correspond to) into four nested types by restricting the form of productions $\alpha \to \beta$. Each class strictly contains the next:

$$\text{Type 3} \subset \text{Type 2} \subset \text{Type 1} \subset \text{Type 0}.$$

Type 0 — Unrestricted (Recursively Enumerable)

• Productions: $\alpha \to \beta$ with $\alpha,\beta \in (V\cup T)^*$ and $\alpha$ containing at least one variable. No restriction.
• Language class: Recursively enumerable languages.
• Automaton: Turing Machine.
• Example: Any TM-recognisable language, e.g. $\{a^n b^n c^n d^n \mid n\ge 1\}$ via context-sensitive-style rules with deletion; e.g. $S \to aSBC,\ \dots,\ CB \to BC,\ aB\to ab,\dots$ (with extra erasing rules).

Type 1 — Context-Sensitive

• Productions: $\alpha \to \beta$ with $|\alpha| \le |\beta|$ (non-contracting); equivalently $\alpha A \beta \to \alpha\gamma\beta$ with $\gamma\ne\varepsilon$. ($S\to\varepsilon$ allowed if $S$ unused on RHS.)
• Language class: Context-sensitive languages.
• Automaton: Linear Bounded Automaton (LBA) — a TM whose tape is bounded by the input length.
• Example: $L=\{a^n b^n c^n \mid n\ge 1\}$, generated by a context-sensitive grammar such as $S\to abc \mid aSBc,\ cB\to Bc,\ bB\to bb$.

Type 2 — Context-Free

• Productions: $A \to \gamma$ where $A\in V$ (single variable on the left) and $\gamma\in(V\cup T)^*$.
• Language class: Context-free languages.
• Automaton: Pushdown Automaton (PDA).
• Example: $\{a^n b^n \mid n\ge 1\}$, generated by $S \to aSb \mid ab$.

Type 3 — Regular

• Productions: right-linear $A \to aB$ or $A\to a$ (or all left-linear), $a\in T,\ A,B\in V$.
• Language class: Regular languages.
• Automaton: Finite Automaton (DFA/NFA).
• Example: $a^*b$ (strings of $a$'s ending in one $b$), generated by $S \to aS \mid b$.

Summary table

(a) Even number of 0's and ending in 1

A block containing an even number of 0's (any number of 1's interspersed) is described by $(1^*0\,1^*0\,1^*)^*$, i.e. 0's come in pairs. The string must then end in 1, so append at least one 1:

$$\boxed{\,(\,1^*0\,1^*0\,)^* \, 1^* 1\,}$$

Equivalently $1^*(0\,1^*0\,1^*)^*1$. This guarantees an even count of 0's and a final symbol 1.

(b) Arden's Theorem

Statement. For regular expressions $P$ and $Q$ where $P$ does not contain (does not generate) the empty string $\varepsilon$, the equation

$$R = Q + RP$$

has the unique solution

$$R = Q P^*.$$

Applying it to the given automaton

States: start $q_1$, final $q_2$. Transitions: $q_1\xrightarrow{a}q_1$, $q_1\xrightarrow{b}q_2$, $q_2\xrightarrow{a}q_2$, $q_2\xrightarrow{b}q_2$.

Write equations for strings reaching each state (each variable = set of strings ending in that state):

$$q_1 = \varepsilon + q_1 a \qquad q_2 = q_1 b + q_2(a+b)$$

Solve $q_1$ with Arden ($Q=\varepsilon,\ P=a$):

$$q_1 = \varepsilon\, a^* = a^*.$$

Solve $q_2$ ($Q=q_1 b = a^*b,\ P=a+b$):

$$q_2 = (a^* b)(a+b)^*.$$

Since $q_2$ is the only final state, the regular expression accepted by the automaton is

$$\boxed{\,a^* b\,(a+b)^*\,}$$

i.e. all strings consisting of zero or more $a$'s, then a $b$, then any string over $\{a,b\}$.

Pumping Lemma for Regular Languages

If $L$ is regular, then there exists a constant $p\ge 1$ (the pumping length) such that every string $w\in L$ with $|w|\ge p$ can be written as

$$w = xyz$$

satisfying:

1. $|y| \ge 1$ (the middle part is non-empty),
2. $|xy| \le p$ (the pumped part lies within the first $p$ symbols),
3. $x y^i z \in L$ for all $i \ge 0$ (pumping keeps the string in $L$).

Proof that $L = \{a^n b^n \mid n \ge 0\}$ is not regular

Assume $L$ is regular, and let $p$ be the pumping length.

Choose the string

$$w = a^{p} b^{p} \in L, \qquad |w| = 2p \ge p.$$

By the lemma, $w = xyz$ with $|xy|\le p$ and $|y|\ge 1$. Since the first $p$ symbols of $w$ are all $a$'s, both $x$ and $y$ lie entirely within the $a$-block. So

$$x = a^{j},\quad y = a^{k}\ (k\ge 1),\quad z = a^{\,p-j-k} b^{p}.$$

Pump with $i = 2$:

$$x y^{2} z = a^{j} a^{2k} a^{\,p-j-k} b^{p} = a^{\,p+k} b^{p}.$$

Since $k\ge 1$, this string has more $a$'s than $b$'s, so $a^{p+k}b^{p} \notin L$. This contradicts condition 3 of the pumping lemma.

Therefore our assumption is false, and $L = \{a^n b^n \mid n\ge 0\}$ is not regular. $\blacksquare$

(a) Ambiguous grammar

A context-free grammar $G$ is ambiguous if there exists at least one string $w \in L(G)$ that has two or more distinct parse (derivation) trees — equivalently, two distinct leftmost (or two distinct rightmost) derivations.

Showing $E \to E + E \mid E * E \mid (E) \mid id$ is ambiguous using the string id + id * id:

Parse tree 1 (addition at the root — interprets as id + (id * id)):

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

Parse tree 2 (multiplication at the root — interprets as (id + id) * id):

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

Both trees derive the same string id + id * id but have different structure (and different evaluation: $id+(id\cdot id)$ vs $(id+id)\cdot id$). Two distinct parse trees exist, hence the grammar is ambiguous.

(b) Removing the ambiguity

The ambiguity is removed by encoding operator precedence and associativity into the grammar using a hierarchy of non-terminals (one level per precedence) and making them left-recursive for left associativity:

E -> E + T | T        (+ has lowest precedence, left-associative)
T -> T * F | F        (* binds tighter than +)
F -> ( E ) | id       (highest precedence: parentheses / atoms)

Now id + id * id has a unique parse tree: $F$/* (the $T$ level) must be built before $+$ (the $E$ level), forcing the multiplication to be grouped first ($id + (id*id)$). Since every string now has exactly one parse tree, the grammar is unambiguous.

Convert to Chomsky Normal Form

Given grammar:

$$S \to ASA \mid aB, \quad A \to B \mid S, \quad B \to b \mid \varepsilon$$

CNF requires every production to be of the form $A \to BC$ (two variables) or $A \to a$ (single terminal); only the start symbol may derive $\varepsilon$, and it must not appear on any right-hand side.

Step 1 — Add a new start symbol

$$S_0 \to S, \quad S \to ASA \mid aB, \quad A \to B \mid S, \quad B \to b \mid \varepsilon$$

Step 2 — Remove $\varepsilon$-productions

Nullable variables: $B$ (directly), and $A$ (via $A\to B$). Remove $B\to\varepsilon$ and add versions of rules with nullable symbols omitted:

• $S\to ASA$: omitting nullable $A$'s gives $S\to SA,\ AS,\ S$.
• $S\to aB$: omitting $B$ gives $S\to a$.
• $A\to B$: $B$ nullable but dropping it gives empty, not added (would be $A\to\varepsilon$, discard).

Result:

$$S_0\to S,\quad S\to ASA\mid SA\mid AS\mid S\mid aB\mid a,\quad A\to B\mid S,\quad B\to b$$

Step 3 — Remove unit productions

Unit pairs and substitution:

• $S\to S$: delete (trivial).
• $S_0\to S$ ⇒ $S_0$ inherits $S$'s rules: $S_0\to ASA\mid SA\mid AS\mid aB\mid a$.
• $A\to B$ ⇒ $A\to b$; $A\to S$ ⇒ $A$ inherits $S$'s rules: $A\to ASA\mid SA\mid AS\mid aB\mid a$.

Now:

$$\begin{aligned} 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 ASA \mid SA \mid AS \mid aB \mid a \mid b\\ B &\to b \end{aligned}$$

Step 4 — Replace terminals in long rules and break up bodies of length > 2

Introduce $T_a \to a$ and use it inside mixed/long bodies. Replace $aB$ with $T_a B$. Break the ternary $ASA$ by introducing $C \to SA$, so $ASA \to A\,C$.

Let $C \to SA$.

Final 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 $X\to YZ$ or $X\to a$, so the grammar is in Chomsky Normal Form.

Mealy vs Moore machines (output behaviour)

Moore machine: residue of a binary number mod 3

Reading the binary input most-significant bit first, the value-so-far $v$ updates as $v \to 2v + \text{bit}$, so the remainder mod 3 updates as $r \to (2r+\text{bit}) \bmod 3$. Use three states, one per residue, and output the residue of the state.

States / outputs: $q_0$ (residue 0, output 0), $q_1$ (residue 1, output 1), $q_2$ (residue 2, output 2). Start state $q_0$ (empty input ⇒ residue 0).

Transition table (next state $=(2r+b)\bmod 3$):

Reasoning for $q_1$ on input 0: $r=1\Rightarrow 2\cdot1+0=2\equiv2\Rightarrow q_2$. On input 1: $2\cdot1+1=3\equiv0\Rightarrow q_0$. Similarly for the others.

Example: input 110 (decimal 6). $q_0\xrightarrow{1}q_1\xrightarrow{1}q_0\xrightarrow{0}q_0$, final output 0 = $6 \bmod 3$. Correct. Because it is a Moore machine, the output is simply the label of the state reached after reading the whole string.

(a) Recursive vs Recursively Enumerable languages

Key fact: $L$ is recursive iff both $L$ and its complement $\bar L$ are recursively enumerable.

(b) Rice's Theorem

Statement. Any non-trivial property of the language recognised by a Turing machine is undecidable. A property $P$ of r.e. languages is non-trivial if it is true for at least one r.e. language and false for at least one other (i.e. neither always true nor always false). Formally, the set

$$\{\langle M\rangle \mid L(M) \text{ has property } P\}$$

is undecidable whenever $P$ is non-trivial.

Example of an undecidable property (by Rice's theorem):

• "Is $L(M) = \emptyset$?" (the emptiness problem) — non-trivial, hence undecidable.

Other consequences: "Is $L(M)$ regular?", "Is $L(M)$ finite?", "Does $L(M)$ contain a particular string $w$?" — all undecidable, since each is a non-trivial property of the recognised language.

(a) DPDA vs NPDA

Unlike finite automata (where DFA = NFA in power), for PDAs NPDA is strictly more powerful than DPDA: e.g. the language of even-length palindromes $\{ww^R \mid w\in\Sigma^*\}$ is context-free but not deterministic context-free.

(b) Pumping Lemma for Context-Free Languages

If $L$ is context-free, there is a constant $p\ge1$ (pumping length) such that every $z\in L$ with $|z|\ge p$ can be written as

$$z = uvwxy$$

satisfying:

1. $|vwx| \le p$,
2. $|vx| \ge 1$ (i.e. $v$ and $x$ are not both empty),
3. $u v^{i} w x^{i} y \in L$ for all $i \ge 0$.

How it is used (proof by contradiction). To show a language $L$ is not context-free:

1. Assume $L$ is context-free with pumping length $p$.
2. Choose a specific string $z\in L$ with $|z|\ge p$ (chosen cleverly).
3. For every allowed decomposition $z=uvwxy$ with $|vwx|\le p$ and $|vx|\ge1$, find some $i$ (usually $i=0$ or $i=2$) such that $uv^iwx^iy \notin L$.
4. This contradicts condition 3, so the assumption fails and $L$ is not context-free.

Illustration: for $L=\{a^n b^n c^n\mid n\ge1\}$, take $z=a^pb^pc^p$; since $|vwx|\le p$, $vwx$ spans at most two of the three symbol blocks, so pumping ($i=2$) unbalances the counts and the result leaves $L$ — proving $L$ is not context-free.