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

Formal Definition of a Turing Machine

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

where:

• $Q$ = finite set of states
• $\Sigma$ = input alphabet (does not contain the blank $B$)
• $\Gamma$ = tape alphabet, with $\Sigma \subseteq \Gamma$ and $B \in \Gamma$
• $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ = transition function
• $q_0 \in Q$ = start state
• $B$ = blank symbol
• $F \subseteq Q$ = set of accepting (final) states

A TM reads/writes on an infinite tape and moves its head left ($L$) or right ($R$). The language accepted is $L(M) = \{ w \in \Sigma^* \mid q_0 w \vdash^* \alpha\, q_f\, \beta,\ q_f \in F \}$.

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

This is a classic non-context-free language; a single-tape TM accepts it.

Strategy: In each pass, mark the leftmost unmarked $a$ as $X$, then move right to mark the leftmost unmarked $b$ as $Y$, then the leftmost unmarked $c$ as $Z$. Return to the left and repeat until all symbols are marked. Finally verify nothing is left over.

States: $Q = \{q_0, q_1, q_2, q_3, q_4, q_5\}$, with $q_5$ the accept state. Tape symbols $X, Y, Z$ are markers for matched $a, b, c$.

Transition function $\delta$:

Working:

1. $q_0$: replace an $a$ by $X$, enter $q_1$. If it instead sees $Y$ (all $a$'s already marked) it goes to the verification state $q_4$.
2. $q_1$: skip remaining $a$'s and already-placed $Y$'s, replace the first $b$ by $Y$, enter $q_2$.
3. $q_2$: skip remaining $b$'s and $Z$'s, replace the first $c$ by $Z$, move left into $q_3$.
4. $q_3$: walk left over $a,b,Y,Z$ until the rightmost $X$ is found, step right and return to $q_0$ to start the next pass.
5. $q_4$ (verification): only $Y$'s and $Z$'s should remain; on reading blank $B$ go to accept state $q_5$. Any leftover $a$, $b$ or $c$ causes a halt with no accepting transition (reject).

The machine accepts only strings with equal numbers of $a$, $b$, $c$ in the order $a^nb^nc^n$.

Transition Diagram (description)

Nodes $q_0 \to q_1 \to q_2 \to q_3 \to q_0$ form the marking loop; an arrow from $q_0$ on input $Y$ goes to $q_4$, and from $q_4$ on $B$ to the double-circle accept state $q_5$. Self-loops on $q_1,q_2,q_3,q_4$ represent skipping over symbols.

Regular Expressions and Finite Automata

Regular expressions (RE) and finite automata (FA) are equivalent in expressive power: a language is regular iff it is described by some regular expression, iff it is accepted by some finite automaton (Kleene's Theorem).

• For every FA there exists an equivalent RE (state-elimination / Arden's theorem).
• For every RE there exists an equivalent $\varepsilon$-NFA (Thompson's construction).

Every RE has an equivalent $\varepsilon$-NFA (Thompson's Construction)

We prove by structural induction on the RE. Each constructed NFA has exactly one start and one accept state.

Base cases:

• $\varnothing$: start and (separate) accept state, no transitions.
• $\varepsilon$: start $\xrightarrow{\varepsilon}$ accept.
• $a \in \Sigma$: start $\xrightarrow{a}$ accept.

Inductive cases (let $N(R)$ be the NFA for $R$):

• Union $R_1 + R_2$: new start with $\varepsilon$-moves to the starts of $N(R_1), N(R_2)$; their accepts have $\varepsilon$-moves to a new accept.
• Concatenation $R_1 R_2$: accept of $N(R_1)$ gets an $\varepsilon$-move to the start of $N(R_2)$.
• Kleene star $R_1^*$: new start $\xrightarrow{\varepsilon}$ start of $N(R_1)$ and $\xrightarrow{\varepsilon}$ new accept; accept of $N(R_1)$ loops back $\xrightarrow{\varepsilon}$ to its start and $\xrightarrow{\varepsilon}$ to the new accept.

By induction, every RE is converted into an $\varepsilon$-NFA accepting the same language. $\blacksquare$

Converting $(a+b)^*ab$ to a Finite Automaton

$\varepsilon$-NFA (Thompson): Build $(a+b)^*$ as a loop that reads any number of $a$'s and $b$'s, then concatenate the literals $a$ then $b$.

After eliminating $\varepsilon$-moves and applying the subset construction we obtain a clean DFA. The language is all strings over $\{a,b\}$ that end in $ab$.

DFA:

• $A$: have not yet seen a pending $a$.
• $B$: last symbol read was $a$ (possible prefix of $ab$).
• $C$ (accepting): string just ended in $ab$.

This DFA accepts exactly $L\big((a+b)^*ab\big)$.

The Halting Problem

Statement: Given an arbitrary Turing Machine $M$ and an input $w$, determine whether $M$ halts (stops) when run on $w$. As a language:

The Halting Problem asks for an algorithm (a TM) that decides membership in $HALT_{TM}$ for every input.

Proof that the Halting Problem is Undecidable

We use proof by contradiction (diagonalization / reduction).

1. Assume a TM $H$ exists that decides the halting problem:

$H$ always halts and gives the correct answer.

2. Construct a new TM $D$ that takes a single TM encoding $\langle M \rangle$ as input and does:

   • Run $H$ on $\langle M, \langle M\rangle \rangle$ (i.e., does $M$ halt on its own description?).
   • If $H$ says "halts" $\Rightarrow$ $D$ loops forever.
   • If $H$ says "loops" $\Rightarrow$ $D$ halts.

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

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

Both cases are contradictory, so the assumption that $H$ exists is false. Hence no TM can decide the Halting Problem; it is undecidable. $\blacksquare$

Decidable vs Undecidable Problems

Note: A problem can be recursively enumerable (a TM accepts all yes-instances but may loop on no-instances) yet still undecidable — the Halting Problem is exactly such a case.

Greibach Normal Form (GNF)

A CFG is in GNF if every production has the form:

where $a$ is a single terminal and $\alpha$ is a (possibly empty) string of variables ($\alpha \in V^*$). Each production starts with exactly one terminal followed by zero or more non-terminals.

Conversion Procedure

1. Pre-process: Eliminate $\varepsilon$-productions, unit productions, and useless symbols, then convert the grammar to Chomsky Normal Form (CNF) as a starting point.
2. Order the variables $A_1, A_2, \dots, A_n$.
3. Remove left recursion and forward substitution: Rewrite productions so that for every $A_i \rightarrow A_j\,\gamma$, we have $j > i$.
   • If $A_i \rightarrow A_j\gamma$ with $j < i$, substitute all productions of $A_j$ into $A_i$.
   • If $A_i \rightarrow A_i\gamma$ (left recursion), eliminate it by introducing a new variable $B_i$:

4. Make leading symbols terminal: Starting from the highest-numbered variable $A_n$ (whose productions already begin with a terminal), back-substitute downward so that every $A_i$ production begins with a terminal.
5. Fix the new $B_i$ variables the same way so their productions also begin with terminals.

Example

For $S \rightarrow Sa \mid b$ (left-recursive):

• Eliminate left recursion: $S \rightarrow b \mid bA$, $A \rightarrow a \mid aA$.
• Both productions now begin with a terminal — this is in GNF.

Use: GNF guarantees each derivation step consumes exactly one terminal, which is useful for constructing a PDA and for proving that every CFL has a PDA (and bounds derivation length to $|w|$ steps).

Instantaneous Description (ID) of a PDA

A Pushdown Automaton is $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$. An instantaneous description captures the complete configuration of the PDA at a moment in time. It is a triple:

where:

• $q \in Q$ = current state,
• $w \in \Sigma^*$ = remaining (unread) portion of the input,
• $\gamma \in \Gamma^*$ = current contents of the stack (top written leftmost).

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

The reflexive-transitive closure $\vdash^*$ denotes zero or more moves.

Acceptance by Final State

The PDA accepts $w$ if, starting from the initial ID, it can consume all of $w$ and reach a final state (stack contents irrelevant):

Acceptance by Empty Stack

The PDA accepts $w$ if, after consuming all of $w$, the stack becomes empty (final state irrelevant):

Equivalence

Both modes accept exactly the context-free languages. For any PDA accepting by final state there is an equivalent PDA accepting by empty stack, and vice versa, so the two acceptance criteria are equivalent in power.

Multi-tape Turing Machine

A multi-tape TM has $k$ tapes ($k \ge 1$), each with its own independent read/write head. It is defined like a standard TM except the transition function is:

Working

1. Input: The input is placed on tape 1; the other tapes start blank.
2. Reading: In one step the machine reads the symbols under all $k$ heads simultaneously (one symbol per tape).
3. Action: Based on the current state and the $k$-tuple of scanned symbols, it:
   • changes state,
   • writes a new symbol on each tape, and
   • moves each head independently left ($L$), right ($R$), or keeps it stationary ($S$).
4. Tapes are used as scratch/work space (e.g., one tape for input, one for a counter, one for output), which makes algorithms much easier to design.

Equivalence with a Single-Tape TM

A multi-tape TM is no more powerful than a single-tape TM; both accept exactly the recursively enumerable languages.

• A single-tape TM can simulate a $k$-tape TM by storing the $k$ tapes on one tape using tracks, marking each head position, and sweeping across to gather symbols.
• Cost: If a $k$-tape TM runs in time $T(n)$, the single-tape simulation runs in $O(T(n)^2)$ time.

Thus multi-tape TMs improve convenience and efficiency, not computational power.

Universal Turing Machine (UTM)

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

$U$ accepts $\langle M, w\rangle$ iff $M$ accepts $w$, halts iff $M$ halts, and loops iff $M$ loops.

How it Works

$U$ typically uses multiple tracks/tapes to store: (1) the encoded transition table of $M$, (2) the current tape contents of $M$, and (3) the current state of $M$. It repeatedly looks up the matching transition of $M$ in the description, updates the simulated tape, state and head position, and continues until $M$ halts.

Significance

• Stored-program concept: A UTM is the theoretical basis of the modern general-purpose, programmable computer — program and data are both stored as input. This directly inspired the von Neumann architecture.
• Universality: It shows one fixed machine can compute anything any TM can compute, supporting the Church–Turing thesis.
• Undecidability: The existence of the UTM enables key undecidability proofs, since its acceptance language $L_u = \{\langle M, w\rangle \mid M \text{ accepts } w\}$ is recursively enumerable but not recursive (undecidable), central to proving the Halting Problem undecidable.

Recursive vs Recursively Enumerable Languages

Both are defined by Turing machines, but differ in halting behaviour.

• Recursive language (Decidable): A language $L$ is recursive if there exists a TM (a decider) that always halts — it accepts every $w \in L$ and rejects (halts) every $w \notin L$.
• Recursively Enumerable (RE) language (Turing-recognizable): A language $L$ is RE if there exists a TM that accepts every $w \in L$, but on $w \notin L$ it may either reject or loop forever.

Key theorem: $L$ is recursive iff both $L$ and its complement $\bar{L}$ are recursively enumerable. The Halting language is RE but not recursive, proving recursive $\subsetneq$ RE.

Mealy and Moore Machines

Both are finite-state machines with output (transducers). A general definition is the 6-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$, where $\Delta$ is the output alphabet and $\lambda$ is the output function — the two differ in $\lambda$.

Moore Machine

Output depends only on the current state:

Each state is labelled with an output symbol. For an input of length $n$, the output length is $n+1$ (the start state's output is emitted before any input).

Mealy Machine

Output depends on both the current state and the current input:

Outputs are written on the transitions. For an input of length $n$, the output length is $n$.

Differences

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

Closure Properties of Regular Languages

A class of languages is closed under an operation if applying that operation to regular languages always yields a regular language. Regular languages are closed under all the following operations. Let $L_1, L_2$ be regular.

1. Union — $L_1 \cup L_2$ is regular. (RE: $R_1 + R_2$; or product/parallel NFA.)
2. Concatenation — $L_1 L_2$ is regular. (RE: $R_1 R_2$.)
3. Kleene Star — $L_1^*$ is regular. (RE: $R_1^*$.)
4. Complementation — $\bar{L_1} = \Sigma^* - L_1$ is regular. (Take the DFA and swap accepting/non-accepting states.)
5. Intersection — $L_1 \cap L_2$ is regular. (Product automaton; or via $\overline{\bar{L_1} \cup \bar{L_2}}$ by De Morgan.)
6. Difference — $L_1 - L_2 = L_1 \cap \bar{L_2}$ is regular.
7. Reversal — $L_1^R$ is regular. (Reverse all transitions, swap start/final states.)
8. Homomorphism and inverse homomorphism — regular languages are closed under both.

Significance: These properties let us prove a language regular by building it from known regular languages, and the decision/closure under intersection & complement is heavily used (e.g., for the product construction and for proving non-regularity by combining with the pumping lemma).

Membership Problem

The membership problem asks: given a grammar $G$ (or automaton) and a string $w$, does $w \in L(G)$? For context-free grammars this is decidable — the CYK algorithm answers it in polynomial time.

CYK (Cocke–Younger–Kasami) Algorithm

CYK is a bottom-up dynamic-programming parser that decides whether $w \in L(G)$, where $G$ must be in Chomsky Normal Form (productions of the form $A \to BC$ or $A \to a$). For $w = a_1 a_2 \dots a_n$ it builds a triangular table $V_{i,j}$ = the set of variables that derive the substring of length $j$ starting at position $i$.

Steps:

1. Length-1: For each symbol $a_i$, set $V_{i,1} = \{ A \mid A \to a_i \in G \}$.
2. Longer substrings: For length $j = 2 \dots n$ and start $i$, examine every split point $k$ ($1 \le k < j$):

3. Acceptance: $w \in L(G)$ iff the start symbol $S \in V_{1,n}$ (the cell covering the whole string).

Complexity: $O(n^3 \cdot |G|)$ time, $O(n^2)$ space — polynomial, so the membership problem for CFLs is decidable.

for i = 1 to n:                      // base case
    V[i][1] = { A : A -> a_i }
for j = 2 to n:                      // substring length
  for i = 1 to n-j+1:                // start position
    for k = 1 to j-1:                // split point
      if A->BC, B in V[i][k], C in V[i+k][j-k]:
        add A to V[i][j]
accept if S in V[1][n]

NFA for $(0+1)^*1$

The regular expression $(0+1)^*1$ describes all strings over $\{0,1\}$ that end with $1$.

NFA $M = (\{q_0, q_1\}, \{0,1\}, \delta, q_0, \{q_1\})$:

• $q_0$ is the start state. On both $0$ and $1$ it can stay in $q_0$ (the $(0+1)^*$ loop), and on $1$ it may also non-deterministically move to $q_1$.
• $q_1$ is the single accepting state, reached only after reading a final $1$.

Transition table:

Transition diagram (description): A self-loop on $q_0$ labelled $0,1$ (for $(0+1)^*$); an arrow $q_0 \xrightarrow{1} q_1$; $q_1$ is a double circle (accepting) with no outgoing edges.

Verification: A string is accepted iff there is a path ending in $q_1$, i.e. iff the last symbol read was $1$ — exactly $L((0+1)^*1)$. For example, 101 is accepted, 110 is rejected.