About this previous year paper
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
| No. | Question | Explanation |
|---|---|---|
| (a) | Design DFA for even number of a’s and even number of b’s | Create 4 states representing combinations of even/odd counts of ‘a’ and ‘b’. Accept if both counts are even. |
| (b) | Identify language accepted by given DFA | Analyze final states and transitions — likely represents pattern-based regular language (e.g., strings ending with “ab” or containing even number of symbols). |
| (c) | Pumping Lemma Theorem | For any regular language L, ∃p ≥ 1 (pumping length) such that any string w in L with |
| (d) | Convert FA to Left Linear Grammar | Each state = non-terminal; transitions define productions. Final states → ε-productions. |
| (e) | Ambiguity Check of Grammar (R → R+R / RR / R* / a / b / c) | The grammar generates arithmetic expressions; it’s ambiguous as the same expression (like a+b*c) has multiple parse trees. |
| (f) | Strings from Grammar (S→aB/bA; A→a/aS/bAA; B→b/bS/aBB) | Generates combinations of ‘a’ and ‘b’ with nested recursions, e.g., aab, abb, bba, etc. |
| (g) | Define PDA and draw diagram | PDA = 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F) with stack operations; used for context-free languages. |
| (h) | PDA for Balanced Parentheses | Push ‘(’ and pop for ‘)’. Accept when stack empty at end of input. |
| (i) | Eliminate Unit Productions | Replace A→B with A→productions of B. Example: S→A/bb, A→B/b, B→S/a → simplified grammar without single non-terminal transitions. |
| (j) | Checking-off Symbols in TM | Symbols used by a Turing machine to mark already-processed input symbols during computation (e.g., replacing ‘1’ with ‘X’ after reading). |
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
| Concept | Key Idea |
|---|---|
| Automata | DFA, NFA, ε-NFA conversions, minimization |
| Regular Languages | Regular expressions, closure, pumping lemma |
| CFG & PDA | Conversion, derivations, ambiguity, CNF |
| Turing Machines | Design, simulation, and undecidability |
| Computation Theory | Halting problem, recursive languages |