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

(a) NFA Definition and Difference from DFA

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

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

where:

• $Q$ — a finite set of states,
• $\Sigma$ — a finite input alphabet,
• $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^{Q}$ — the transition function mapping a state and an input symbol (or $\varepsilon$) to a set of states,
• $q_0 \in Q$ — the start state,
• $F \subseteq Q$ — the set of accepting (final) states.

Differences from a DFA:

Both recognize exactly the same class — the regular languages — but the NFA is often easier to design.

(b) NFA for strings containing substring 011

States: $q_0$ (start), $q_1$ (seen 0), $q_2$ (seen 01), $q_3$ (seen 011, accepting).

$q_0$ loops on both symbols (guessing the start of the pattern); once 011 is found, $q_3$ absorbs all further input.

Subset construction (NFA → DFA)

Start with $\{q_0\}$ and compute reachable subsets:

DFA: start state $A$; accepting states $D, E, F$ (every subset containing $q_3$).

Resulting DFA state diagram (described)

• $A \xrightarrow{0} B$, $A \xrightarrow{1} A$
• $B \xrightarrow{0} B$, $B \xrightarrow{1} C$
• $C \xrightarrow{0} B$, $C \xrightarrow{1} D$ (accept)
• $D,E,F$ are accepting and never leave the accepting region: each transitions among $\{D,E,F\}$, so once 011 has appeared the string is accepted regardless of the suffix.

This DFA accepts exactly the strings over $\{0,1\}$ containing 011.

(a) CFG, PDA, and their Equivalence

Context-Free Grammar (CFG): a 4-tuple $G = (V, T, P, S)$ where $V$ is a finite set of variables (non-terminals), $T$ the set of terminals ($V\cap T=\varnothing$), $P$ a finite set of productions of the form $A \to \alpha$ with $A\in V$ and $\alpha\in(V\cup T)^*$, and $S\in V$ the start symbol. The language is $L(G)=\{w\in T^*\mid S \Rightarrow^* w\}$.

Pushdown Automaton (PDA): a 7-tuple $M = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, i.e. an NFA augmented with a stack, where $\Gamma$ is the stack alphabet, $Z_0$ the initial stack symbol, and $\delta: Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma \to 2^{Q\times\Gamma^*}$.

Equivalence: A language is context-free iff it is accepted by some PDA. Every CFG can be converted to an equivalent PDA (and vice versa). Moreover, acceptance by final state and acceptance by empty stack define the same class of languages. Hence CFGs and PDAs have exactly the same expressive power (the context-free languages).

(b) Grammar $S \to aSb \mid ab$

It generates $L=\{a^nb^n\mid n\ge 1\}$:

By induction. Base: $S\Rightarrow ab = a^1b^1$. Inductive step: applying $S\to aSb$ to $a^{n}b^{n}$ wraps one $a$ on the left and one $b$ on the right, giving $a^{n+1}b^{n+1}$. Every derivation must end with $S\to ab$, so every generated string has the form $a^nb^n$ ($n\ge1$), and each such string is derivable by $n-1$ uses of $S\to aSb$ then $S\to ab$. Therefore $L(G)=\{a^nb^n\mid n\ge1\}$. $\blacksquare$

PDA accepting by empty stack. Idea: push a marker for each $a$, pop one for each matching $b$.

$M=(\{q_0,q_1\},\{a,b\},\{A,Z_0\},\delta,q_0,Z_0,\varnothing)$ with transitions:

1. delta(q0, a, Z0) = { (q0, A Z0) }   ; first a: push A
2. delta(q0, a, A)  = { (q0, A A)  }   ; more a's: push A
3. delta(q0, b, A)  = { (q1, e)    }   ; first b: pop one A
4. delta(q1, b, A)  = { (q1, e)    }   ; more b's: pop A
5. delta(q1, e, Z0) = { (q1, e)    }   ; pop Z0 -> empty stack, accept

(Here e = $\varepsilon$.) After reading all $a$'s the stack holds $A^nZ_0$; each $b$ pops one $A$; if counts match, after the last $b$ the stack is $Z_0$, which rule 5 pops, emptying the stack and accepting. Unequal counts leave the stack non-empty or block a transition, so they are rejected.

(a) Standard Turing Machine and the Church-Turing Thesis

A (single-tape) Turing Machine is a 7-tuple:

$$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$$

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

The machine has a two-way infinite tape and a read/write head. It halts when it enters $q_{accept}$ or $q_{reject}$; otherwise it may loop forever.

Church-Turing Thesis: every function that is effectively computable (computable by any mechanical/algorithmic procedure) can be computed by a Turing machine. Equivalently, the Turing machine captures the intuitive notion of an algorithm; all reasonable models of computation (λ-calculus, recursive functions, RAM, etc.) are equivalent in power to it. It is a thesis (not a provable theorem) because "effectively computable" is an informal notion.

(b) Turing Machine for $L=\{a^nb^nc^n \mid n\ge1\}$

Strategy: repeatedly mark the leftmost unmarked $a$ as $X$, then the leftmost $b$ as $Y$, then the leftmost $c$ as $Z$; return to the start and repeat. Accept when no symbols remain unmarked.

Tape alphabet $\Gamma=\{a,b,c,X,Y,Z,\sqcup\}$. Transition function:

q0: a -> X,R,q1        ; mark an a, go find a b
    Y -> Y,R,q4        ; all a's done -> verify no extra b/c
q1: a -> a,R,q1        ; skip a's
    Y -> Y,R,q1        ; skip already-marked Y's
    b -> Y,R,q2        ; mark a b, go find a c
q2: b -> b,R,q2        ; skip b's
    Z -> Z,R,q2        ; skip already-marked Z's
    c -> Z,L,q3        ; mark a c, go back
q3: a,b,c,Y,Z -> same,L,q3   ; sweep left
    X -> X,R,q0        ; back to start, repeat
q4: Y -> Y,R,q4        ; skip Y's
    Z -> Z,R,q4        ; skip Z's
    blank -> blank,R,qaccept   ; nothing left -> accept

Any symbol read in a state with no rule (e.g. a stray $a$, $b$, or $c$ in $q4$, or a missing $b$/$c$) leads to $q_{reject}$.

Trace on input aabbcc

All three symbols are consumed in equal numbers, so the machine accepts aabbcc ($n=2$).

(a) Regular Expression Operators: Precedence and Meaning

For expressions over an alphabet $\Sigma$, the three operators in decreasing order of precedence are:

1. Kleene star $r^{*}$ — zero or more repetitions of $r$ (highest precedence). Meaning: $L(r^*)=\bigcup_{i\ge0}L(r)^i$.
2. Concatenation $r_1 r_2$ — a string of $r_1$ followed by a string of $r_2$. Meaning: $L(r_1r_2)=L(r_1)L(r_2)$.
3. Union (alternation) $r_1 \mid r_2$ — a string in $r_1$ or $r_2$ (lowest precedence). Meaning: $L(r_1\mid r_2)=L(r_1)\cup L(r_2)$.

Parentheses override precedence. Also $\varepsilon$ denotes the empty string and $\varnothing$ the empty language. Example: $a\mid bc^*$ means $a\mid(b(c^*))$.

(b) Regular Expressions

(i) Strings over $\{0,1\}$ of length a multiple of 3:

$$\big((0\mid1)(0\mid1)(0\mid1)\big)^{*}$$

Each group contributes exactly 3 symbols, so the total length is $0,3,6,\dots$ (note $\varepsilon$ of length 0 is included).

(ii) Strings over $\{a,b\}$ that begin and end with the same symbol:

$$a\,(a\mid b)^{*}\,a \;\mid\; b\,(a\mid b)^{*}\,b \;\mid\; a \;\mid\; b$$

The first two alternatives cover strings of length $\ge2$ with matching ends; the single symbols $a$ and $b$ cover length-1 strings (whose first and last symbol coincide trivially).

Pumping Lemma for Regular Languages

If $L$ is regular, then there exists a constant $p\ge1$ (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$,
3. for all $i \ge 0$, $xy^{i}z \in L$.

Proof that $L=\{a^nb^n \mid n\ge0\}$ is not regular

Assume, for contradiction, that $L$ is regular. Let $p$ be the pumping length. Choose

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

By the lemma, $w=xyz$ with $|xy|\le p$ and $|y|\ge1$. Since the first $p$ symbols of $w$ are all $a$'s, the substring $xy$ lies entirely within the $a$-block, so $y$ consists only of $a$'s: $y=a^{k}$ with $1\le k\le p$.

Now pump with $i=2$:

$$xy^{2}z = a^{p+k}b^{p}.$$

Here the number of $a$'s is $p+k > p$ = the number of $b$'s, so $xy^2z \notin L$.

This contradicts condition 3 of the pumping lemma. Hence our assumption is false, and $L=\{a^nb^n\mid n\ge0\}$ is not regular. $\blacksquare$

Chomsky Hierarchy of Grammars

Noam Chomsky classified grammars into four nested types by restricting the form of productions ($A,B$ = variables, $a$ = terminal, $\alpha,\beta,\gamma$ = strings of symbols).

The classes are strictly nested: Regular $\subset$ Context-Free $\subset$ Context-Sensitive $\subset$ Recursively Enumerable.

Examples:

• Type 3 (Regular): $S\to aS \mid b$ generates $a^*b$. Accepted by a finite automaton.
• Type 2 (Context-Free): $S\to aSb \mid \varepsilon$ generates $\{a^nb^n\mid n\ge0\}$ (not regular). Accepted by a PDA.
• Type 1 (Context-Sensitive): a grammar for $\{a^nb^nc^n\mid n\ge1\}$ (not context-free). Accepted by a linear-bounded automaton.
• Type 0 (Unrestricted): grammars generating any recursively enumerable language, e.g. encoding an arbitrary Turing machine's computation. Accepted by a Turing machine.

Ambiguous Grammar

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

The grammar $E \to E+E \mid E*E \mid (E) \mid id$ is ambiguous

Consider the string $id + id * id$. It has two different leftmost derivations / parse trees:

Derivation 1 (treats + as the outer operator → $id+(id*id)$):

$$E \Rightarrow E+E \Rightarrow id+E \Rightarrow id+E*E \Rightarrow id+id*E \Rightarrow id+id*id$$

Parse tree: root + with left child $id$ and right child the subtree $E*E$.

Derivation 2 (treats * as the outer operator → $(id+id)*id$):

$$E \Rightarrow E*E \Rightarrow E+E*E \Rightarrow id+E*E \Rightarrow id+id*E \Rightarrow id+id*id$$

Parse tree: root * with left child the subtree $E+E$ and right child $id$.

Two distinct parse trees for the same string ⇒ the grammar is ambiguous.

Removing the Ambiguity

Rewrite the grammar to enforce operator precedence (* binds tighter than +) and left-associativity, using separate non-terminals for each precedence level:

$$E \to E + T \mid T \qquad T \to T * F \mid F \qquad F \to (E) \mid id$$

Now $id+id*id$ has a unique parse tree (with $id*id$ grouped first), so the grammar is unambiguous.

Decidable vs Undecidable Problems

A decidable (recursive) problem is one for which there exists an algorithm (a Turing machine) that halts on every input and correctly answers "yes" or "no". Example: "Does a DFA accept a given string?"

An undecidable problem is one for which no such always-halting algorithm exists; no Turing machine can decide all instances correctly. Example: the Halting Problem.

The Halting Problem

Statement: Given an arbitrary Turing machine (program) $M$ and an input $w$, decide whether $M$ halts (terminates) when run on $w$. Formally, decide membership in $HALT = \{\langle M,w\rangle \mid M \text{ halts on } w\}$.

Why it is Undecidable (essential argument)

Suppose, for contradiction, a TM $H$ decides $HALT$: $H(\langle M,w\rangle)$ = yes if $M$ halts on $w$, no otherwise (and $H$ always halts).

Build a machine $D$ that takes $\langle M\rangle$ and does:

D(<M>):
  if H(<M>, <M>) = yes  then  loop forever
  else                       halt

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

• If $D$ halts on $\langle D\rangle$, then $H(\langle D\rangle,\langle D\rangle)=$ yes, so by construction $D$ loops — contradiction.
• If $D$ loops on $\langle D\rangle$, then $H(\langle D\rangle,\langle D\rangle)=$ no, so by construction $D$ halts — contradiction.

Either case is contradictory, so the assumed $H$ cannot exist. This diagonalization argument proves the Halting Problem is undecidable. $\blacksquare$

Constructing the Finite Automaton

The right-linear grammar is:

$$S \to aA \mid bS \mid \varepsilon, \qquad A \to aS \mid bA$$

Map each variable to a state ($S\to$ state $S$, $A\to$ state $A$); a production $X\to cY$ gives a transition $X\xrightarrow{c}Y$, and $X\to\varepsilon$ makes $X$ an accepting state.

• $S\to aA$ ⟹ $S\xrightarrow{a}A$
• $S\to bS$ ⟹ $S\xrightarrow{b}S$
• $S\to\varepsilon$ ⟹ $S$ is a final state
• $A\to aS$ ⟹ $A\xrightarrow{a}S$
• $A\to bA$ ⟹ $A\xrightarrow{b}A$

Transition table (start = $S$, final = $\{S\}$):

This is a DFA with two states.

Language Accepted

Reading a $b$ never changes the state ($S\to S$, $A\to A$); reading an $a$ toggles between $S$ and $A$. So the automaton is in state $A$ exactly when the number of $a$'s read so far is odd, and in $S$ (the accepting state) when it is even.

Therefore the accepted language is:

$$L = \{\, w \in \{a,b\}^{*} \mid w \text{ contains an even number of } a\text{'s} \,\}$$

(the number of $b$'s is unrestricted, and $\varepsilon$, with zero $a$'s, is accepted).

Converting to Chomsky Normal Form

Start grammar:

$$S\to ASB\mid\varepsilon,\quad A\to aAS\mid a,\quad B\to SbS\mid A\mid bb$$

Step 1 — Add a new start symbol

$S_0\to S$, keeping all old rules (so the start symbol never appears on a RHS).

Step 2 — Remove $\varepsilon$-productions

Nullable variables: $S$ (from $S\to\varepsilon$). $B$ has $B\to SbS$ but $b$ is terminal, so $B$ is not nullable; $A$ is not nullable. Remove $S\to\varepsilon$ and add versions of rules with $S$ omitted:

• $S\to ASB$ ⟹ also $S\to AB$ (drop the $S$)
• $A\to aAS$ ⟹ also $A\to aA$
• $B\to SbS$ ⟹ also $B\to bS,\ Sb,\ b$
• $S_0\to S$ ⟹ also $S_0\to\varepsilon$ (kept, since $\varepsilon\in L$)

Now:

$$S_0\to S\mid\varepsilon,\quad S\to ASB\mid AB,\quad A\to aAS\mid aA\mid a,\quad B\to SbS\mid bS\mid Sb\mid b\mid A\mid bb$$

Step 3 — Remove unit productions

Unit pairs: $S_0\to S$ and $B\to A$.

• Replace $S_0\to S$ by $S$'s rules: $S_0\to ASB\mid AB$ (and keep $S_0\to\varepsilon$).
• Replace $B\to A$ by $A$'s rules: $B\to aAS\mid aA\mid a$.

Result:

$$S_0\to ASB\mid AB\mid\varepsilon,\quad S\to ASB\mid AB,\quad A\to aAS\mid aA\mid a,$$ $$B\to SbS\mid bS\mid Sb\mid b\mid bb\mid aAS\mid aA$$

Step 4 — Replace terminals in long RHS

Introduce $X_a\to a$ and $X_b\to b$, substituting them wherever a terminal sits in a string of length $\ge2$:

• $A\to X_aAS\mid X_aA\mid a$
• $B\to SX_bS\mid X_bS\mid SX_b\mid b\mid X_bX_b\mid X_aAS\mid X_aA$
• $S_0\to ASB\mid AB\mid\varepsilon$, $S\to ASB\mid AB$

Step 5 — Break RHS longer than 2 into binary

Introduce auxiliary variables for length-3 right-hand sides:

• $ASB$: let $C_1\to SB$, then $S_0\to AC_1$, $S\to AC_1$.
• $X_aAS$: let $C_2\to AS$, then $A\to X_aC_2$, $B\to X_aC_2$.
• $SX_bS$: let $C_3\to X_bS$, then $B\to SC_3$.

Final CNF grammar

$$\begin{aligned} S_0&\to AC_1\mid AB\mid\varepsilon\\ S&\to AC_1\mid AB\\ A&\to X_aC_2\mid X_aA\mid a\\ B&\to SC_3\mid X_bS\mid SX_b\mid X_aC_2\mid X_aA\mid X_bX_b\mid b\\ C_1&\to SB,\quad C_2\to AS,\quad C_3\to X_bS\\ X_a&\to a,\quad X_b\to b \end{aligned}$$

Every production now has the form $A\to BC$ or $A\to a$ (with the single allowed exception $S_0\to\varepsilon$ because the start symbol does not appear on any RHS), so the grammar is in CNF.

Recursive vs Recursively Enumerable Languages

Recursive (decidable) language: a language $L$ for which there is a Turing machine that always halts and decides membership — it accepts every $w\in L$ and rejects (halts and says "no") every $w\notin L$.

Recursively enumerable (RE / Turing-recognizable) language: a language $L$ for which there is a Turing machine that accepts (halts) every $w\in L$, but on $w\notin L$ it may either reject or loop forever (run without halting).

Why Recursive ⟹ Recursively Enumerable

If $L$ is recursive, it has a decider $M$ that halts on all inputs. This same $M$ is also a recognizer: it accepts exactly the strings of $L$ (and halts on them). A decider is a special case of a recognizer, so every recursive language is recursively enumerable.

Why the Converse Fails

There exist RE languages that are not recursive — the classic example is

$$A_{TM}=\{\langle M,w\rangle \mid M \text{ accepts } w\}.$$

A universal TM can recognize $A_{TM}$ (simulate $M$ on $w$ and accept if it accepts), so it is RE. But it is undecidable (no always-halting decider exists, by the Halting Problem). Hence it is RE but not recursive.

Key theoretical fact: $L$ is recursive iff both $L$ and its complement $\overline{L}$ are recursively enumerable. If "RE ⟹ recursive" held for all languages, every RE language would be decidable, contradicting the existence of $A_{TM}$. Therefore RE is a strictly larger class, and the converse does not hold.