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

Complexity Classes P and NP

Class P (Polynomial time): P is the set of all decision problems (languages) that can be decided by a deterministic Turing machine in time bounded by a polynomial in the input size $n$. Formally, $P = \bigcup_{k\ge 0} \text{TIME}(n^k)$. These are the problems regarded as efficiently solvable. Examples: shortest path, sorting, primality testing, 2-SAT.

Class NP (Nondeterministic Polynomial time): NP is the set of decision problems that can be decided by a nondeterministic Turing machine in polynomial time, or equivalently the set of problems whose YES-instances have a certificate (proof) that can be verified by a deterministic TM in polynomial time. Examples: SAT, Hamiltonian cycle, vertex cover, subset-sum.

Clearly $P \subseteq NP$ (a solver can ignore the certificate). Whether $P = NP$ is the famous open problem.

Polynomial-Time Reduction

A language $A$ is polynomial-time (many-one / Karp) reducible to $B$, written $A \le_p B$, if there is a function $f$ computable in polynomial time such that for every string $w$:

If $A \le_p B$ and $B \in P$, then $A \in P$. Reductions let us prove a new problem is hard by transforming a known hard problem into it.

NP-Completeness

A language $B$ is NP-complete if:

1. $B \in NP$, and
2. NP-hardness: every language $A \in NP$ satisfies $A \le_p B$.

NP-complete problems are the hardest problems in NP: if any one of them has a polynomial-time algorithm, then $P = NP$. To prove a new problem $C$ is NP-complete we show $C \in NP$ and reduce a known NP-complete problem to $C$ ($\text{known} \le_p C$).

SAT and the Cook–Levin Theorem

Boolean Satisfiability (SAT): Given a Boolean formula $\phi$ over variables $x_1,\dots,x_n$, decide whether there is a truth assignment making $\phi$ true.

• SAT $\in$ NP: a satisfying assignment is a certificate; substituting it and evaluating $\phi$ takes polynomial time.
• Cook–Levin Theorem (1971): SAT is NP-complete. The proof shows that for any $A \in NP$ decided by a polynomial-time NTM $M$, the entire accepting computation (a tableau of configurations) can be encoded by a Boolean formula $\phi_w$ of polynomial size that is satisfiable iff $M$ accepts $w$. Hence $A \le_p \text{SAT}$ for all $A \in NP$.

Thus SAT was the first proven NP-complete problem; all other NP-completeness proofs (3-SAT, clique, vertex cover, etc.) follow by chains of polynomial reductions starting from SAT.

DFA Minimization by the Table-Filling (Partitioning) Method

Goal: Given a DFA $M = (Q, \Sigma, \delta, q_0, F)$, produce an equivalent DFA with the minimum number of states by merging indistinguishable states.

Two states $p, q$ are distinguishable if there exists a string $w$ such that exactly one of $\hat\delta(p,w),\ \hat\delta(q,w)$ is final.

Algorithm (steps)

1. Remove unreachable states from $q_0$.
2. Build a table of all unordered pairs $\{p,q\}$.
3. Basis: Mark $\{p,q\}$ as distinguishable if one is final and the other is non-final.
4. Induction: For every unmarked pair $\{p,q\}$ and each symbol $a$, if $\{\delta(p,a),\delta(q,a)\}$ is already marked, mark $\{p,q\}$.
5. Repeat step 4 until no new pair gets marked.
6. Merge every pair left unmarked — these are equivalent states — into a single state. Define transitions on the merged blocks; $q_0$'s block is the start, blocks containing final states are final.

Worked Example

Consider DFA with states $A,B,C,D,E$, alphabet $\{0,1\}$, start $A$, final $\{E\}$:

Basis: $E$ is final, all others non-final, so every pair containing $E$ is marked: $\{A,E\},\{B,E\},\{C,E\},\{D,E\}$.

Induction: Check remaining pairs.

• $\{A,C\}$: $0\to(B,B)$ same; $1\to(C,C)$ same → not marked.
• $\{B,D\}$: $1\to(D,E)$ and $\{D,E\}$ is marked → mark $\{B,D\}$.
• $\{A,B\}$: $1\to(C,D)$; $\{C,D\}$? $1\to(C,E)$ marked ⇒ $\{C,D\}$ marked ⇒ $\{A,B\}$ marked.
• Continuing, the only pair that stays unmarked is $\{A,C\}$.

Merge: $A$ and $C$ are equivalent → merge into state $AC$. Minimized DFA states: $\{AC, B, D, E\}$:

This 4-state DFA is the minimal DFA equivalent to the original 5-state DFA.

Note: By the Myhill–Nerode theorem, the minimal DFA is unique up to renaming of states.

Pumping Lemma for Context-Free Languages

Statement: If $L$ is a context-free language, then there exists a constant $p \ge 1$ (the pumping length) such that every string $z \in L$ with $|z| \ge p$ can be written as

satisfying:

1. $|vwx| \le p$,
2. $|vx| \ge 1$ (i.e. $v$ and $x$ are not both empty), and
3. for all $i \ge 0$, $\ uv^iwx^iy \in L$.

Proof Sketch

Let $L = L(G)$ for a CFG $G$ in Chomsky Normal Form with $m$ variables. Take $p = 2^{m}$. Any string $z\in L$ with $|z|\ge p$ has a parse tree of height $> m$. Along the longest root-to-leaf path there are more than $m$ variable nodes, so by the pigeonhole principle some variable $A$ repeats. Let the upper $A$ derive $vwx$ and the lower $A$ derive $w$, with $A \Rightarrow^* vAx \Rightarrow^* vwx$. Then:

• Replacing the lower subtree by the upper one $i$ times gives $A \Rightarrow^* v^i w x^i$, hence $z_i = uv^iwx^iy \in L$ for all $i\ge0$ (condition 3).
• Because CNF rules branch into two, the repetition can be found within the bottom portion so $|vwx|\le p$ (condition 1).
• The rule $A \Rightarrow vAx$ uses a binary production, so $vx$ produces at least one symbol, giving $|vx|\ge 1$ (condition 2).

Showing $L = \{a^i b^j c^k \mid i = j = k\}$ is NOT Context-Free

Assume for contradiction $L$ is CFL with pumping length $p$. Choose

Write $z = uvwxy$ with $|vwx|\le p$ and $|vx|\ge 1$.

Since $|vwx| \le p$, the substring $vwx$ spans at most two of the three symbol blocks (it cannot contain $a$'s and $c$'s simultaneously, because they are separated by $p$ b's).

Pump with $i = 2$, giving $z_2 = uv^2wx^2y$:

• If $vx$ contains only $a$'s and $b$'s (or any mix avoiding $c$), then $z_2$ has more $a$'s and/or $b$'s but the same number of $c$'s, so the counts are no longer equal.
• Symmetrically, if $vx$ avoids $a$'s, the number of $a$'s stays $p$ while $b$/$c$ counts increase.

In every case at least one symbol's count differs from the others, so $z_2 \notin L$. This contradicts the pumping lemma.

Conclusion: No such $p$ exists, therefore $L = \{a^ib^jc^k \mid i=j=k\}$ is not context-free. $\blacksquare$

DFA Accepting Binary Strings Ending in '00'

Let $M = (Q,\Sigma,\delta,q_0,F)$ with $\Sigma=\{0,1\}$.

• $q_0$: no useful suffix yet (last symbol not a 0 toward goal),
• $q_1$: the string so far ends in a single '0',
• $q_2$: the string ends in '00' (accepting).

Transition table:

Start state $q_0$; accepting state $F=\{q_2\}$.

Idea: On a '1' the suffix is broken, so go back to $q_0$. On a '0' advance ($q_0\to q_1\to q_2$); once in $q_2$, a further '0' keeps it in $q_2$ (suffix still '00').

Check: 100 → $q_0\to q_0\to q_1\to q_2$ (accept). 1001 → ends in $q_0$ (reject). Correct.

ε-closure

In an ε-NFA, the ε-closure of a state $q$, written $\varepsilon\text{-CLOSURE}(q)$, is the set of all states reachable from $q$ using only ε (empty) transitions, including $q$ itself.

Formally it is the smallest set $S$ such that $q \in S$ and if $r \in S$ then every state in $\delta(r,\varepsilon)$ is also in $S$. For a set of states $T$, $\varepsilon\text{-CLOSURE}(T)=\bigcup_{q\in T}\varepsilon\text{-CLOSURE}(q)$.

It is used in subset (NFA-to-DFA) construction and in defining the extended transition $\hat\delta$ for ε-NFAs.

Example

Consider states with ε-moves: $q_0 \xrightarrow{\varepsilon} q_1$, $q_1 \xrightarrow{\varepsilon} q_2$, and $q_2$ has no ε-move.

• $\varepsilon\text{-CLOSURE}(q_0) = \{q_0, q_1, q_2\}$ (reach $q_1$ then $q_2$ via ε).
• $\varepsilon\text{-CLOSURE}(q_1) = \{q_1, q_2\}$.
• $\varepsilon\text{-CLOSURE}(q_2) = \{q_2\}$ (no outgoing ε-edge).

Thus from $q_0$ the machine can be in any of $\{q_0,q_1,q_2\}$ without consuming input.

Regular Expression: at least one 0 AND at least one 1

Over $\Sigma=\{0,1\}$, a string must contain a 0 somewhere and a 1 somewhere. A 0 and a 1 must appear in some order, so:

• First term: a $0$ appears before a $1$.
• Second term: a $1$ appears before a $0$.

Together they cover every string having at least one 0 and at least one 1.

Equivalent compact form (complement of "all 0's or all 1's"):

Examples accepted: 01, 10, 1100, 0110. Rejected: 000, 111, \varepsilon.

Arden's Theorem

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

has the unique solution

(The condition $\varepsilon\notin L(P)$ guarantees uniqueness.)

Use: Finding a Regular Expression from a Finite Automaton

For a DFA/NFA, write one equation per state $q_i$ describing the set of strings that lead from the start state into $q_i$ (or, in the alternative formulation, from $q_i$ to a final state):

Wherever an equation has the self-referential form $q = q P + Q$, apply Arden's theorem to replace it by $q = QP^*$. Substituting back and repeatedly eliminating variables, the equation for the final state(s) yields a regular expression equal to $\sum$ of the languages, i.e. $L(M)$.

Short Example

FA: start $A$ with $A\xrightarrow{a}A$, $A\xrightarrow{b}B$, $B$ final. Equations: $A = \varepsilon + Aa$, $B = Ab$. Apply Arden's to $A = \varepsilon + Aa$ (here $P=a$, $Q=\varepsilon$): $A = \varepsilon\,a^* = a^*$. Then $B = a^*b$. So $L(M) = a^*b$.

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 trees (equivalently, two distinct leftmost — or two distinct rightmost — derivations). Ambiguity is a property of the grammar, not the language.

Example

Consider the expression grammar:

Take the string $w = id + id * id$.

Parse tree 1 (treats $+$ as outer operator — corresponds to $id + (id * id)$):

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

Leftmost derivation: $E \Rightarrow E+E \Rightarrow id+E \Rightarrow id+E*E \Rightarrow id+id*E \Rightarrow id+id*id$.

Parse tree 2 (treats $*$ as outer operator — corresponds to $(id + id) * id$):

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

Leftmost derivation: $E \Rightarrow E*E \Rightarrow E+E*E \Rightarrow id+E*E \Rightarrow id+id*E \Rightarrow id+id*id$.

The same string $id+id*id$ has two different parse trees / leftmost derivations, so the grammar is ambiguous. (Ambiguity here can be removed by introducing precedence/associativity via separate non-terminals for term and factor.)

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

The production is immediately left-recursive because the right side $Aa$ begins with the non-terminal $A$ itself.

General rule: For $A \rightarrow A\alpha \mid \beta$ (where $\beta$ does not start with $A$), rewrite as

Here $\alpha = a$ and $\beta = b$. Introducing a new non-terminal $A'$:

Verification: The original generates $b a^*$ (a $b$ followed by zero or more $a$'s). The new grammar: $A \Rightarrow bA' \Rightarrow b\,a\,A' \Rightarrow \dots \Rightarrow b a^n$, also generating $\{ba^n \mid n\ge 0\}$. The languages match and the new grammar is right-recursive (no left recursion), suitable for top-down (LL) parsing.

Greibach Normal Form (GNF)

A CFG is in Greibach Normal Form if every production has the form

where $a$ is a single terminal and $\alpha$ is a (possibly empty) string of non-terminals ($\alpha \in V^*$). Thus each production starts with exactly one terminal followed by zero or more variables. (For a language containing $\varepsilon$, $S\to\varepsilon$ is allowed with $S$ not on any RHS.)

GNF guarantees each derivation step generates exactly one terminal symbol, which is useful for showing CFL = NPDA and for top-down parsing.

Conversion Procedure

1. Convert to Chomsky Normal Form (CNF) first: remove ε-productions, unit productions, and useless symbols, and ensure productions are $A\to BC$ or $A\to a$.
2. Order the non-terminals $A_1, A_2, \dots, A_n$.
3. Remove left recursion / substitute so that every production $A_i \to A_j \gamma$ has $j > i$: for each $i$, for each $j<i$, substitute the productions of $A_j$ into $A_i \to A_j\gamma$. Then eliminate any immediate left recursion on $A_i$ by introducing a new variable $B_i$ ($A_i \to A_i\alpha$ becomes $A_i\to\beta B_i$, $B_i\to\alpha B_i \mid \alpha$).
4. After this, $A_n$'s productions already start with a terminal. Back-substitute: working downward ($A_{n-1}, \dots, A_1$ and the $B_i$), replace a leading non-terminal at the start of any RHS by its productions, so every production begins with a terminal.

Small Example

$S \to AB,\ A\to a,\ B\to b$. Substitute $A\to a$ into $S\to AB$: $S \to aB$. Now all productions ($S\to aB,\ A\to a,\ B\to b$) begin with a terminal — GNF achieved.

Instantaneous Description (ID) of a PDA

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

where

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

A move between IDs is written with the turnstile $\vdash$:

$\vdash^*$ denotes zero or more moves. The initial ID is $(q_0, w, Z_0)$.

Acceptance by Final State

The language accepted by final state is

The input is accepted if, after consuming the whole input, the PDA is in some final state — the stack contents are irrelevant.

Acceptance by Empty Stack

The language accepted by empty stack is

The input is accepted if, after consuming the whole input, the stack becomes empty — the final state is irrelevant ($F$ is typically taken as $\emptyset$).

Equivalence: The two acceptance modes accept exactly the same class of languages (the context-free languages); a PDA of one type can be converted to one of the other.

Multi-Tape Turing Machine

A multi-tape Turing machine is a TM equipped with $k \ge 1$ semi-infinite (or two-way infinite) tapes, each with its own independent read/write head. It is a convenient model that is equivalent in power to the standard single-tape TM.

Components / Working

• It has a finite control (set of states), and $k$ tapes; tape 1 initially holds the input, the other tapes are blank.
• In one move, depending on the current state and the $k$ symbols currently scanned (one per tape), the machine:
  1. Writes a symbol on each of the $k$ tapes (independently),
  2. Moves each of the $k$ heads independently Left, Right, or Stays (L/R/S), and
  3. Enters a new state.
• The transition function has the form

• Acceptance is by entering an accept (halt) state, as usual.

Advantage

Separating data onto different tapes makes algorithm design much simpler (e.g. one tape for input, one as a counter/scratchpad). It can speed computation up by a polynomial factor.

Equivalence with Single-Tape TM

Any $k$-tape TM $M$ can be simulated by a single-tape TM $S$: $S$ stores the $k$ tape contents on one tape using $2k$ tracks — $k$ tracks for the symbols and $k$ tracks marking each head position. To simulate one move of $M$, $S$ sweeps across to read all $k$ marked symbols, then sweeps back updating symbols and head markers. Hence multi-tape TMs recognize exactly the recursively enumerable languages — the same class as single-tape TMs — though a single-tape simulation of $t$ steps may take $O(t^2)$ time.