THEORY EXAMINATION (SEM–IV) 2016-17 THEORY OF AUTOMATA AND FORMAL LANGUAGES

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

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