About this previous year paper
Course: B.Tech (CSE / IT)
Subject Code: ECS403
Subject Title: Theory of Automata and Formal Languages
Exam Type: Theory
Duration: 3 Hours
Maximum Marks: 100
SECTION – A (10 × 2 = 20 Marks)
Short theoretical and concept-based questions that test fundamentals
| No. | Question | Explanation |
|---|---|---|
| (a) | Design DFA for even number of a’s and b’s | Construct 4-state DFA to track parity of a’s and b’s — transitions based on input symbols. |
| (b) | Identify language accepted by given DFA | Analyze accepting states and transitions to describe L (usually pattern-based like strings ending in a specific sequence). |
| (c) | Pumping Lemma for Regular Languages | If L is regular, ∃p ≥ 1 such that ∀w ∈ L with |
| (d) | Convert FA to Left Linear Grammar | Replace each state by non-terminal and transitions as productions → convert machine to equivalent grammar. |
| (e) | Check Ambiguity of Grammar (R → R+R / RR / R* / a / b / c) | Grammar generates expressions like a+b*c; ambiguous if multiple parse trees possible for same string. |
| (f) | Generate Strings from Grammar | Grammar rules generate patterns like aab, abb, etc. Use derivation sequence. |
| (g) | Define PDA with Diagram | PDA = 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F); shown using transition diagram (stack-based). |
| (h) | PDA for Balanced Parentheses | Stack-based PDA: push ‘(’ on stack; pop for ‘)’; accept if stack empty at end. |
| (i) | Eliminate Unit Productions | Simplify grammar (replace A → B by A → productions of B). |
| (j) | Checking-off Symbols | Symbols used in Turing Machine tape to mark already-processed input symbols. |
SECTION – B (5 × 10 = 50 Marks)
Medium-length analytical and proof-based questions
(a) NFA-ε to DFA Conversion
Step 1: Compute ε-closure for all states.
Step 2: Use subset construction to form equivalent DFA.
Step 3: Merge identical states.
(Page 2 shows example diagrams of automata equivalence).
(b) Closure Properties of Regular Languages
Regular languages closed under:
Union, Intersection, Complement
Concatenation, Kleene Star
Homomorphism and Inverse Homomorphism
Proof: Use DFA construction or regular expressions to demonstrate closure.
(c) Kleene’s Theorem
States equivalence between:
Regular expressions
Finite Automata
Regular languages
Example: Convert DFA → Regular Expression via Arden’s theorem.
(d) Grammar Derivation
Given: S → aSS, A → b
Derive string aababbb using leftmost and rightmost derivation, and draw the parse tree.
(e)
(i) Determine if L={xnynzn∣n≥1}L = \{x^n y^n z^n | n ≥ 1\}L={xnynzn∣n≥1} is context-free.
→ Not context-free (proved by Pumping Lemma for CFLs).
(ii) Construct PDA for L={wwR∣w∈(a+b)∗}L = \{ww^R | w ∈ (a+b)^*\}L={wwR∣w∈(a+b)∗}.
→ Push first half on stack, pop while matching reverse.
(f) Convert CFG to CNF
Example:
S→XY∣Xn∣p,X→mX∣m,Y→Xn∣oS → XY | Xn | p, \quad X → mX | m, \quad Y → Xn | oS→XY∣Xn∣p,X→mX∣m,Y→Xn∣o
and
S→ASA∣aB,A→B∣S,B→b∣εS → ASA | aB, \quad A → B | S, \quad B → b | εS→ASA∣aB,A→B∣S,B→b∣ε
→ Eliminate ε-productions and unit productions; ensure RHS ≤ 2 symbols.
(g) Turing Machine (TM) for Odd Number of a’s
Read input; toggle a parity flag.
Accept if odd flag ON at end.
(Diagram on page 2 shows TM design).
(h) Halting Problem
Statement: No algorithm can decide for every TM whether it halts on input w.
Proof by contradiction using diagonalization (similar to Cantor’s theorem).
SECTION – C (2 × 15 = 30 Marks)
Long, problem-solving questions involving Automata, PDA, and TM design
Q3.
(a) Minimize the given DFA (see diagram on page 3).
Steps:
Group states by final/non-final.
Eliminate indistinguishable states via equivalence partitioning.
Redraw minimized DFA.
(b) Compute ε-closure for NFA and convert to DFA using subset method.
Q4.
(a) Construct PDA for L={0n1n∣n>0}L = \{0^n 1^n | n > 0\}L={0n1n∣n>0}.
→ Push 0’s; pop for each 1; accept if stack empty.
(b) Build PDA from CFG:
S→XS∣ε,A→aXb∣Ab∣abS → XS | ε, \quad A → aXb | Ab | abS→XS∣ε,A→aXb∣Ab∣ab
Use transitions based on productions to derive equivalent PDA.
Q5.
(a) Prove that single-tape TM can simulate multi-tape TM —
→ Encode multiple tape contents on one tape with delimiters.
→ Simulation possible with polynomial time overhead.
(b) Design TM for strings with odd number of α’s (proof of computability).
Summary Table
| Concept | Example / Problem Type |
|---|---|
| Regular Languages | DFA/NFA design, closure properties |
| CFGs & CNF | Conversion, ambiguity, derivation trees |
| Pushdown Automata | Balanced parentheses, equal 0s & 1s |
| Turing Machines | Recognition, computation, simulation |
| Undecidability | Halting problem, reduction proofs |