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

Context-Free Grammar (CFG)

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, with $V \cap T = \varnothing$
• $P$ = finite set of productions of the form $A \to \alpha$, where $A \in V$ and $\alpha \in (V \cup T)^*$
• $S \in V$ = the start symbol

It is context-free because the left side of every production is a single variable, so a variable can be replaced regardless of context.

Converting to Chomsky Normal Form (CNF)

A grammar is in CNF if every production has the form $A \to BC$ (two variables) or $A \to a$ (single terminal). Given grammar:

Step 1 — Add a new start symbol. Introduce $S_0 \to S$ so the start symbol never appears on a right side.

Step 2 — Remove $\varepsilon$-productions. Nullable variables: $B$ (from $B \to \varepsilon$), and $A$ (since $A \to B$). Remove $B \to \varepsilon$ and add all combinations omitting nullable symbols:

• $S \to ASA$ gives $S \to ASA \mid SA \mid AS \mid S$ (dropping one or both $A$'s).
• $S \to aB$ gives $S \to aB \mid a$.
• $A \to B$ stays; nothing new since $B$ has a non-empty body.

Resulting set:

Step 3 — Remove unit productions. Units are $S_0 \to S,\ S \to S,\ A \to B,\ A \to S$. Drop $S \to S$ (trivial). Substitute the bodies:

• $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$ (from $A \to B \to b$) and $A \to ASA \mid SA \mid AS \mid aB \mid a$ (from $A \to S$)
• $B \to b$

Step 4 — Replace terminals in long bodies. Introduce $T_a \to a$ and replace $a$ in $aB$ by $T_a$, giving bodies $T_aB$.

Step 5 — Break bodies longer than 2. For $ASA$, introduce $A_1 \to SA$, so $ASA \to A\,A_1$.

Final CNF Grammar

Every production now has the form $A \to BC$ or $A \to a$, so the grammar is in Chomsky Normal Form and generates the same language as the original.

Pushdown Automaton (PDA)

A Pushdown Automaton is a finite automaton augmented with an auxiliary stack (LIFO) memory, which gives it more power than a finite automaton and lets it recognize 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 \subseteq Q$ = accepting states

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

Idea: push a marker for each $a$, then pop one for each $b$; accept when input ends and the stack is back to its bottom.

Let $M = (\{q_0, q_1, q_2\}, \{a,b\}, \{Z_0, A\}, \delta, q_0, Z_0, \{q_2\})$ (acceptance by final state). Transitions:

Trace for the string aabb

ID notation: $(\text{state}, \text{remaining input}, \text{stack})$, stack top on the left.

The input is fully consumed and the machine is in accepting state $q_2$, so aabb is accepted. Hence $M$ accepts $L = \{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 the blank)
• $\Gamma$ = tape alphabet, $\Sigma \subseteq \Gamma$, with blank $B \in \Gamma$
• $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ = transition function (write a symbol, move head Left or Right)
• $q_0 \in Q$ = start state, $B$ = blank symbol, $F \subseteq Q$ = accepting (halting) states

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

Strategy: repeatedly mark the leftmost unmarked $a$ as $X$, the leftmost $b$ as $Y$, the leftmost $c$ as $Z$, then return to the left and repeat. This matches one $a$, one $b$, one $c$ per pass, guaranteeing equal counts in correct order. Accept when only $X, Y, Z$ remain.

States: $q_0$ (find $a$), $q_1$ (scan right for $b$), $q_2$ (scan right for $c$), $q_3$ (return left), $q_4$ (verify all marked), $q_{acc}$.

If at any point the expected symbol is missing (e.g. a $b$ before all $a$'s are matched, or leftover $a/b/c$), no transition applies and the machine halts and rejects.

Transition Diagram (described)

Nodes $q_0 \to q_1 \to q_2 \to q_3 \to q_0$ form a loop: each cycle converts one $a\to X$, one $b\to Y$, one $c\to Z$. The arc $q_0 \to q_4 \to q_{acc}$ (taken when the first remaining symbol is $Y$ and the rest are only $Y,Z,B$) leads to the accepting state. Self-loops on $q_1, q_2, q_3$ skip over already-marked or not-yet-needed symbols.

Working on aabbcc

Pass 1: $\underline{a}abbcc \Rightarrow XaYbZc \dots$ — first $a,b,c$ marked. Pass 2: remaining $a,b,c$ marked as $X,Y,Z$. Tape becomes $XXYYZZ$; in $q_4$ the head scans only $Y,Z$ then a blank, reaching $q_{acc}$. Thus the string is accepted.

Because this TM both writes and reads and may visit a cell many times, it recognizes the context-sensitive / recursively enumerable language $L$, which is not context-free.

We need strings over $\{0,1\}$ containing at least one 0 and at least one 1. A clean regular expression is:

The first term covers strings where some 0 appears before some 1; the second covers strings where a 1 appears before a 0. Their union therefore guarantees the presence of both symbols.

(Equivalently, in extended notation: all strings except those with no 0 or no 1, i.e. $(0+1)^* \setminus (1^* + 0^*)$.)

Arden's Theorem

Statement: Let $P$ and $Q$ be two regular expressions over an alphabet $\Sigma$. If $P$ does not contain the empty string $\varepsilon$ (i.e. $\varepsilon \notin P$), then the equation

has a unique solution:

Use in Obtaining a Regular Expression from a Finite Automaton

For a finite automaton, write one equation per state describing the strings that reach that state. For each state $q$, its equation is the sum, over all incoming transitions, of (source-state expression $\cdot$ input symbol); the start state's equation also includes $\varepsilon$.

This yields a system of simultaneous equations of the form $R = Q + RP$. Using Arden's theorem, we repeatedly substitute and solve each self-referential equation by replacing $R = Q + RP$ with $R = QP^*$, eliminating variables one by one. The expression finally obtained for the final (accepting) state is the regular expression denoting the language accepted by the automaton.

Why the $\varepsilon \notin P$ condition matters: it ensures uniqueness; if $P$ contained $\varepsilon$, infinitely many solutions would satisfy the equation.

Ambiguous Grammar

A context-free grammar $G$ is said to be ambiguous if there exists at least one string $w \in L(G)$ that has two or more distinct derivation trees (equivalently, two distinct leftmost or two distinct rightmost derivations). Ambiguity is a property of the grammar, not of the language.

Example

Consider the expression grammar:

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

Parse 1 (treats $+$ as the top operator):

Parse 2 (treats $*$ as the top operator):

Since the same string $id + id * id$ admits two distinct parse trees (one grouping as $id + (id * id)$, the other as $(id + id) * id$), the grammar is ambiguous.

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

The production $A \to Aa$ is immediately left-recursive (the variable $A$ appears as the leftmost symbol of its own body).

General rule: a rule of the form

(where $\beta$ does not start with $A$) is rewritten using a new variable $A'$ as:

Applying it here with $\alpha = a$ and $\beta = b$:

This grammar is right-recursive and generates exactly the same language $\{b a^n \mid n \ge 0\}$ (i.e. $b$ followed by zero or more $a$'s), but is now suitable for top-down (e.g. recursive-descent / 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 variables. Thus every body begins with exactly one terminal followed only by non-terminals.

Conversion Procedure (CFG → GNF)

Pre-requisite: first convert the grammar to Chomsky Normal Form and remove $\varepsilon$-productions, unit productions, and useless symbols.

Step 1 — Order the variables. Rename the variables $A_1, A_2, \dots, A_n$.

Step 2 — Make productions increasing in index. Modify productions so that every rule $A_i \to A_j \gamma$ has $j > i$:

• If $j < i$, substitute every production of $A_j$ into the body of $A_i$, then repeat.
• If $j = i$, it is left recursion; eliminate it using a new variable $B_i$:

(where $A_i \to A_i\alpha \mid \beta$).

Step 3 — Make leading symbols terminals (back-substitution). Now $A_n$'s bodies already start with a terminal. Working backwards from $A_n$ to $A_1$, substitute the (already-GNF) productions of $A_j$ into any rule whose body starts with $A_j$, so that every leading symbol becomes a terminal.

Step 4 — Fix the new variables $B_i$. Apply the same back-substitution to the introduced $B_i$ variables so their bodies also begin with a terminal.

The result is an equivalent grammar in GNF. GNF is important because it guarantees each derivation step consumes exactly one input terminal, which directly yields an equivalent PDA and bounds derivation length to $|w|$ steps for a string $w$.

Instantaneous Description (ID) of a PDA

An instantaneous description captures the complete momentary configuration of a PDA. It is a triple:

• $q$ = the current state
• $w$ = the remaining unread input string
• $\gamma$ = the current stack contents (conventionally written with the top of the stack on the left)

A single move is written with the turnstile relation $\vdash$: if $\delta(q, a, Z)$ contains $(p, \beta)$, then

$\vdash^*$ denotes zero or more moves.

Acceptance by Final State

Starting from $(q_0, w, Z_0)$, the PDA accepts $w$ by final state if there is a sequence of moves leading to an accepting state, regardless of the stack contents:

i.e. the whole input is consumed and the machine ends in some final state $p \in F$.

Acceptance by Empty Stack

The PDA accepts $w$ by empty stack if, after consuming all input, the stack becomes completely empty (the set $F$ is irrelevant here):

Equivalence: the two acceptance modes define the same class of languages (the context-free languages); any PDA accepting by final state can be converted to one accepting by empty stack and vice versa.

Multi-Tape Turing Machine

A multi-tape Turing Machine has $k \ge 2$ tapes, each with its own independent read/write head. The machine reads the symbols under all $k$ heads simultaneously and, in one move, can write a new symbol on each tape and move each head independently Left, Right, or stay (S).

Working / Transition Function

For a $k$-tape machine the transition function is

On a single step the control unit, based on the current state and the $k$ scanned symbols $(a_1, \dots, a_k)$, does the following at once:

1. Moves to a new state,
2. Writes a symbol on each of the $k$ tapes,
3. Moves each of the $k$ heads independently.

Initially the input is placed on tape 1 and the other tapes hold blanks; the extra tapes serve as scratch / working memory, which often makes algorithms much simpler to express (e.g. copying, counting, or comparing substrings).

Power

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$ tapes interleaved on one tape with head-position markers). The simulation costs at most a quadratic slowdown ($O(T^2)$ steps to simulate $T$ steps), so the class of languages recognized (recursively enumerable) is identical. Multi-tape machines are mainly a convenience that simplifies design and improves time efficiency.

Universal Turing Machine (UTM)

A Universal Turing Machine is a single Turing Machine $U$ that can simulate the behaviour of any other Turing Machine on any input. It takes as input an encoding $\langle M \rangle$ of an arbitrary TM $M$ together with an encoded input string $w$, written as $\langle M, w \rangle$, and then:

• simulates the computation of $M$ on $w$ step by step, and
• accepts/halts exactly when $M$ would accept/halt on $w$ (and loops if $M$ loops).

Formally, $U$ on $\langle M, w \rangle$ produces the same result that $M$ produces on $w$. $U$ keeps three pieces of information on its tape: the encoded description of $M$, the simulated tape contents of $M$, and $M$'s current state.

Significance

1. Stored-program concept: the UTM shows that a single fixed machine can run any algorithm if the program (the description of $M$) is supplied as data. This is the theoretical foundation of the modern general-purpose, stored-program computer (von Neumann architecture).
2. Existence of a universal model: it proves computation is programmable — one machine, many tasks — rather than needing a new machine per problem.
3. Undecidability: the UTM is central to proving the Halting Problem undecidable; the universal/diagonal construction shows there is no algorithm to decide whether an arbitrary $M$ halts on $w$.
4. It establishes the notion of a recursively enumerable universal language $L_u = \{\langle M, w\rangle \mid M \text{ accepts } w\}$, which is RE but not recursive.

Recursive vs Recursively Enumerable Languages

Both classes are defined in terms of Turing Machines, but differ in whether the TM is guaranteed to halt.

Key theorem: $L$ is recursive iff both $L$ and its complement $\overline{L}$ are recursively enumerable.

Example: $\{a^n b^n c^n \mid n \ge 1\}$ is recursive (decidable). The Halting Problem language is recursively enumerable but not recursive.