BSc CSIT (TU) Science Theory of Computation (BSc CSIT, CSC257) Question Paper 2081 Nepal

Pushdown Automaton (PDA)

A Pushdown Automaton is a finite automaton augmented with an unbounded stack memory. The stack lets it count or match symbols, so a PDA recognizes exactly the context-free languages. Formally it is a 7-tuple:

• $Q$ = finite set of states
• $\Sigma$ = input alphabet
• $\Gamma$ = stack alphabet
• $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to$ finite subsets of $Q \times \Gamma^{*}$ = transition function
• $q_0$ = start state, $Z_0$ = initial stack symbol, $F$ = set of final states

PDA for $L = \{ a^n b^n \mid n \ge 1 \}$

Idea: push one $A$ for every $a$ read; for every $b$ read, pop one $A$. Accept (by final state) when the stack is restored to $Z_0$ after the input ends.

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

1. $\delta(q_0, a, Z_0) = \{(q_0, AZ_0)\}$ — first $a$, push $A$
2. $\delta(q_0, a, A) = \{(q_0, AA)\}$ — more $a$'s, keep pushing
3. $\delta(q_0, b, A) = \{(q_1, \varepsilon)\}$ — first $b$, pop one $A$
4. $\delta(q_1, b, A) = \{(q_1, \varepsilon)\}$ — more $b$'s, keep popping
5. $\delta(q_1, \varepsilon, Z_0) = \{(q_2, Z_0)\}$ — stack empty of $A$'s, accept

Trace for the string aabb

Using instantaneous descriptions $(\text{state}, \text{remaining input}, \text{stack})$ with stack top written leftmost:

The input is fully consumed and the PDA halts in final state $q_2$, so aabb is accepted. Since the number of $a$'s pushed must equal the number of $b$'s popped before reaching $q_2$, $M$ accepts exactly $\{a^n b^n \mid n \ge 1\}$.

Formal Definition of a Turing Machine

A Turing Machine (TM) is a 7-tuple:

• $Q$ = finite set of states
• $\Sigma$ = input alphabet (does not contain blank $B$)
• $\Gamma$ = tape alphabet, $\Sigma \subseteq \Gamma$, $B \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, $B$ = blank symbol, $F$ = set of accepting (halt) states

The TM has an infinite tape and a read/write head; it accepts an input if it halts in a final state. Since $L = \{a^n b^n c^n\}$ is not context-free, a PDA cannot accept it, but a TM can.

TM for $L = \{ a^n b^n c^n \mid n \ge 1 \}$

Strategy: repeatedly cross off one $a$ (mark as $X$), then the matching $b$ (mark $Y$), then the matching $c$ (mark $Z$). Return to the left and repeat until no $a$'s remain. Then verify nothing but $Y/Z$ is left.

States: $\{q_0,q_1,q_2,q_3,q_4,q_5\}$, $q_5$ accepting. Tape alphabet $\{a,b,c,X,Y,Z,B\}$.

q0, a -> q1, X, R     ; mark an a, scan right for a b
q1, a -> q1, a, R
q1, Y -> q1, Y, R
q1, b -> q2, Y, R     ; mark matching b, scan right for a c
q2, b -> q2, b, R
q2, Z -> q2, Z, R
q2, c -> q3, Z, L     ; mark matching c, go back left
q3, (a|b|Y|Z) -> q3, same, L
q3, X -> q0, X, R     ; reached leftmost X, restart on next a
q0, Y -> q4, Y, R     ; no more a's: only Y/Z should remain
q4, Y -> q4, Y, R
q4, Z -> q4, Z, R
q4, B -> q5, B, R     ; ACCEPT (equal counts, correct order)

If at any point the expected symbol is missing (e.g. a $b$ has no matching $c$, or counts differ), $\delta$ is undefined and the machine halts in a non-final state, rejecting the string.

Working / Transition Diagram (described)

Think of a cycle: $q_0 \xrightarrow{a/X,R} q_1 \xrightarrow{b/Y,R} q_2 \xrightarrow{c/Z,L} q_3 \xrightarrow{X/X,R} q_0$. Each pass through the loop converts one $a$, one $b$ and one $c$ into $X,Y,Z$. When $q_0$ instead reads $Y$, the input has been fully matched; it enters $q_4$ to scan the trailing $Y$'s and $Z$'s and, on reading blank $B$, moves to accepting state $q_5$.

Example aabbcc becomes XaYbZc → XXYYZZ after two cycles, then $q_4$ verifies and accepts.

Regular Expressions and Finite Automata

Kleene's Theorem states that a language is regular iff it can be described by a regular expression iff it is accepted by some finite automaton (DFA/NFA/$\varepsilon$-NFA). Thus regular expressions and finite automata have exactly the same expressive power and are inter-convertible:

• RE $\to$ $\varepsilon$-NFA: Thompson's construction.
• NFA/$\varepsilon$-NFA $\to$ DFA: subset construction.
• DFA $\to$ RE: state elimination / Arden's theorem.

For every RE there is an $\varepsilon$-NFA (Thompson's construction)

Proof by induction on the structure of the regular expression $r$. Base cases:

• $r = \varnothing$: an automaton with start and non-accepting state, no transitions.
• $r = \varepsilon$: start state that is also accepting.
• $r = a$ ($a \in \Sigma$): start state with an $a$-edge to a single accepting state.

Inductive step (let $N(s),N(t)$ be $\varepsilon$-NFAs for sub-expressions $s,t$):

• Union $s+t$: new start state with $\varepsilon$-edges to the starts of $N(s)$ and $N(t)$; their accepting states $\varepsilon$-link to a new final state.
• Concatenation $st$: connect the accepting state of $N(s)$ by $\varepsilon$ to the start of $N(t)$.
• Star $s^{*}$: new start/final state, with $\varepsilon$-edges into $N(s)$ and a loop-back $\varepsilon$-edge from its accepting state, plus an $\varepsilon$-edge allowing $\varepsilon$ itself.

Each case preserves the language, so by induction every RE has an equivalent $\varepsilon$-NFA. $\blacksquare$

Converting $(a+b)^{*}ab$ to a finite automaton

The RE means: any string over $\{a,b\}$ ending in ab. A simple NFA (start $q_0$):

$q_0$ loops on $a,b$ (the $(a+b)^{*}$ part) and non-deterministically guesses the final ab by going $q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2$.

Determinized (DFA) by subset construction:

Accepting state $C$ contains $q_2$. This 3-state DFA accepts exactly the strings ending in ab, confirming the equivalence.

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 derivations or two distinct rightmost derivations).

Example

Consider the grammar:

The string id + id * id has two different leftmost derivations / parse trees:

Derivation 1 (group $+$ first):

Parse tree: root +, with right child a * subtree → corresponds to $id + (id * id)$.

Derivation 2 (group $*$ first):

Parse tree: root *, with left child a + subtree → corresponds to $(id + id) * id$.

Since the same string id + id * id yields two distinct parse trees, the grammar is ambiguous. (Ambiguity can often be removed by introducing precedence/associativity, e.g. $E \to E + T \mid T,\ T \to T * F \mid F,\ F \to id$.)

Eliminating Left Recursion from $A \to Aa \mid b$

General rule: for a left-recursive rule $A \to A\alpha \mid \beta$ (where $\beta$ does not start with $A$), replace it with:

Here $\alpha = a$ and $\beta = b$. Substituting:

Verification: the original grammar generates $b a^{*}$ (a $b$ followed by any number of $a$'s). The new grammar derives $A \Rightarrow bA' \Rightarrow b\,a\,A' \Rightarrow \dots \Rightarrow b a^{n}$, the same language, but the new productions are right-recursive, so left recursion has been removed (making the grammar suitable for top-down/LL parsing).

Greibach Normal Form (GNF)

A CFG is in GNF if every production has the form

where $a$ is a single terminal and $\alpha \in V^{*}$ is a (possibly empty) string of non-terminals. The grammar must be $\varepsilon$-free (except possibly $S \to \varepsilon$). GNF guarantees that each derivation step produces exactly one terminal, which is useful for proving the CFG–PDA equivalence and for top-down parsing.

Conversion Procedure

1. Pre-process: remove $\varepsilon$-productions, unit productions, and useless symbols. Convert the grammar to Chomsky Normal Form (CNF) ($A \to BC$ or $A \to a$) as a clean starting point.
2. Order the non-terminals $A_1, A_2, \dots, A_n$.
3. Remove left recursion and substitute so every production's right-hand side starts with a higher-numbered non-terminal. For each $i$, for each rule $A_i \to A_j \gamma$ with $j < i$, replace $A_j$ by all of its right-hand sides. Eliminate any resulting immediate left recursion $A_i \to A_i\alpha \mid \beta$ using a new variable $B_i$: $A_i \to \beta B_i,\ B_i \to \alpha B_i \mid \varepsilon$ (rewritten to avoid $\varepsilon$).
4. Back-substitute from the highest-numbered non-terminal downward. After step 3, $A_n$'s productions begin with a terminal; substitute these into the productions of $A_{n-1}, A_{n-2}, \dots$ so that every production begins with a terminal.
5. Fix the new variables $B_i$ similarly so their productions also begin with a terminal.

The result is an equivalent grammar in which every production is of the form $A \to a\,\alpha$, i.e. in Greibach Normal Form.

Instantaneous Description (ID) of a PDA

An instantaneous description captures the complete configuration of a PDA at a moment in time. It is a triple

• $q$ = current state
• $w$ = the remaining (unread) portion of the input string
• $\gamma$ = current contents of the stack (top symbol written leftmost)

A move is written $(q, aw, X\beta) \vdash (p, w, \alpha\beta)$ when $\delta(q,a,X)$ contains $(p,\alpha)$. The relation $\vdash^{*}$ is the reflexive–transitive closure (zero or more moves).

Acceptance by Final State

The language accepted by final state is:

The input is accepted if, after consuming all of $w$, the PDA is in some accepting state $q \in F$; the stack contents $\gamma$ are irrelevant.

Acceptance by Empty Stack

The language accepted by empty stack is:

Here the input is accepted if, after consuming all of $w$, the stack becomes empty, regardless of the state. The set $F$ is not used.

Note: the two acceptance criteria are equivalent in power — for every PDA accepting by final state there is a PDA accepting the same language by empty stack, and vice versa.

Multi-tape Turing Machine

A multi-tape Turing Machine has $k$ tapes ($k \ge 1$), each with its own independent read/write head. Initially the input is placed on tape 1 and the other tapes are blank.

Transition function: in one step the machine reads the $k$ symbols currently under all heads, and depending on the current state and these $k$ symbols it:

1. changes state,
2. writes a (possibly new) symbol on each of the $k$ tapes,
3. moves each head independently Left, Right, or Stays put.

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

Advantage: extra tapes act as scratch/work space, often making algorithms simpler and faster. For example, $\{a^n b^n c^n\}$ or palindrome checking, or copying data, is much easier with separate work tapes than on a single tape.

Equivalence: a multi-tape TM is no more powerful than a standard single-tape TM. Any $k$-tape TM can be simulated by a single-tape TM (storing the $k$ tracks/head positions on one tape). The simulation is at most a polynomial (quadratic) slowdown: $t$ steps of a $k$-tape machine take $O(t^2)$ steps on the single-tape machine. Hence multi-tape TMs recognize exactly the recursively enumerable languages, confirming the Church–Turing thesis.

Universal Turing Machine (UTM)

A Universal Turing Machine is a single Turing Machine $U$ that can simulate the behaviour of any other Turing Machine $M$ on any input $w$. It takes as input an encoding $\langle M, w \rangle$ — a description of $M$'s states and transition function together with the input $w$ — and then carries out, step by step, exactly what $M$ would do on $w$:

That is, $U$ accepts iff $M$ accepts $w$, halts iff $M$ halts, and loops iff $M$ loops.

Significance

• Programmable / stored-program concept: A single fixed machine can perform any computation by reading a description of the machine to be run as data. This is the theoretical foundation of the general-purpose, stored-program digital computer (von Neumann architecture), where programs and data live in the same memory.
• Universality of computation: It shows that one machine is enough to compute everything computable, supporting the Church–Turing thesis.
• Basis for undecidability: The encoding-and-simulation idea behind the UTM is exactly what makes it possible to prove that the Halting Problem and many other problems are undecidable (by diagonalization / reduction). Hence the UTM is central both to what computers can do and to the limits of what they cannot do.

Recursive vs. Recursively Enumerable Languages

Both classes are defined by Turing Machines, differing in whether the TM is guaranteed to halt.

Key fact: A language $L$ is recursive iff both $L$ and its complement $\overline{L}$ are recursively enumerable. The Halting problem shows the inclusion Recursive $\subsetneq$ Recursively Enumerable is strict.

Mealy and Moore Machines

Both are finite-state machines with output (transducers). They are 6-tuples $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$ where $\Delta$ is the output alphabet and $\lambda$ is the output function; they differ in how $\lambda$ is defined.

Moore machine: output depends only on the current state.

Mealy machine: output depends on the current state and the current input.

Differences

Both machines are equivalent in power — any Mealy machine can be converted to an equivalent Moore machine and vice versa.

Closure Properties of Regular Languages

The class of regular languages is closed under an operation if applying that operation to regular language(s) always yields a regular language. Regular languages are closed under the following operations (each provable by constructing an FA or RE for the result):

1. Union: if $L_1, L_2$ are regular, $L_1 \cup L_2$ is regular. (RE: $r_1 + r_2$; or an NFA with a new start state $\varepsilon$-linked to both.)
2. Concatenation: $L_1 L_2$ is regular. (RE: $r_1 r_2$; link accepting states of $M_1$ to the start of $M_2$.)
3. Kleene Star: $L_1^{*}$ is regular. (RE: $r_1^{*}$.)
4. Complement: $\overline{L_1} = \Sigma^{*} \setminus L_1$ is regular. (Take a complete DFA and swap accepting / non-accepting states.)
5. Intersection: $L_1 \cap L_2$ is regular. (Product/cross construction of the two DFAs; also follows from union + complement by De Morgan: $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$.)
6. Difference: $L_1 - L_2 = L_1 \cap \overline{L_2}$ is regular.
7. Reversal: $L_1^{R}$ is regular. (Reverse all edges, swap start/final.)
8. Homomorphism and inverse homomorphism also preserve regularity.

These closure properties are useful both to prove a language is regular (by building it from known regular pieces) and to prove non-regularity (e.g., if $L \cap R$ were non-regular for a regular $R$, then $L$ cannot be regular).