THEORY EXAMINATION (SEM–IV) 2016-17 THEORY OF COMPUTATION

Course: B.Tech (Computer Science & Engineering)
Subject Code: CS404
Subject Title: Theory of Computation
Exam Type: Theory
Duration: 3 Hours
Maximum Marks: 100

SECTION – A (10 × 2 = 20 Marks)

Short conceptual questions testing key principles of automata theory

SECTION – B (5 × 10 = 50 Marks)

Medium-length analytical questions testing automata transformation and proofs

(a)

(i) Convert NFA–ε to DFA
(ii) Check equivalence of two FA using comparison method (see diagrams on page 2).
→ Uses subset construction and state minimization techniques.

(b) Closure Properties of Regular Languages

Regular languages are closed under:

Union, Intersection, Complement

Concatenation, Kleene Star

Homomorphism and Inverse Homomorphism
Proof: Construct FA for each operation or use regular expressions to demonstrate closure.

(c) Kleene’s Theorem

Establishes equivalence between:

Regular Expressions

Finite Automata

Regular Languages
Example: Conversion DFA → Regular Expression using Arden’s Theorem.

(d) Grammar Derivation Example

Given S → aSS, A → b, derive aababbb using leftmost and rightmost derivations and draw the parse tree.
Demonstrates CFG production sequences and structural parsing.

(e)

(i) Check if L = {xⁿyⁿzⁿ | n ≥ 1} is context-free → Not context-free (proved via Pumping Lemma for CFLs).
(ii) Construct PDA for L = {wwᴿ | w ∈ (a+b)*} → Push first half of string on stack, pop while matching reverse.

(f) CFG → CNF Conversion

Eliminate ε-productions, unit productions, and useless symbols.

Ensure RHS ≤ 2 non-terminals.
Example:

S → XY | Xn | p   X → mX | m   Y → Xn | o 

and

S → ASA | aB   A → B | S   B → b | ε

(g) Turing Machine for Odd Number of α’s

TM reads input, toggles a parity flag for each α, and accepts if it ends in the “odd” state.

(h) Halting Problem Proof

No algorithm can universally determine whether a TM halts on a given input.
Proof by contradiction using diagonalization (similar to Cantor’s proof for uncountability).

 SECTION – C (2 × 15 = 30 Marks)

Long analytical problems with diagrams and derivations

Q3 (a) Minimize DFA

(See diagram on page 3)
Apply equivalence partitioning:

Partition states into final/non-final sets.

Iteratively refine until all distinguishable states are separated.

Redraw minimized DFA.

Q3 (b) Convert NFA to DFA via ε-closure

Compute ε-closure for each state and apply subset construction to generate equivalent deterministic automaton.

Q4. PDA Construction

(a) For L={0n1n∣n>0}L = \{0^n1^n | n > 0\}L={0n1n∣n>0}:
→ Push 0’s onto stack, pop one for each 1, and accept if stack empty.
(b) From CFG:

S→XS∣ε,A→aXb∣Ab∣abS → XS | ε, \quad A → aXb | Ab | abS→XS∣ε,A→aXb∣Ab∣ab

→ Construct equivalent PDA using grammar-to-PDA transition rules.

Q5.

(a) Single Tape vs Multi-Tape Turing Machine
Single-tape TM can simulate multi-tape TM by encoding multiple tape contents with special delimiters.
(b) Design TM for Odd Number of α’s
Define states q₀ (even) and q₁ (odd). Toggle state for each α. Accept if in q₁.

Summary Table