The B.Tech Theory of Automata & Formal Languages (RCS403) question paper from the 2017–18 IV Semester Theory Examination is a comprehensive and analytically oriented 70-mark exam. It evaluates a student’s command over automata theory, formal languages, grammars, Turing machines, closure properties, ambiguity, and computational models. Spread across three extensive sections, the paper demands conceptual clarity, language construction skills, machine design ability, conversions, reductions, and theoretical proofs.
SECTION A – Foundational Concepts (Short Answer Questions, 14 Marks)
This section contains seven 2-mark questions covering essential definitions, basic constructions, and introductory-level automata operations.
Topics include:
Definitions of alphabet, string, and language
Designing a regular expression over {a, b} containing exactly two a’s
Designing an NFA accepting strings containing substring “abba”
Definition of Chomsky Hierarchy
Closure of context-free languages under union (with example)
Converting a given NFA to DFA
Removing useless productions from a provided grammar
This section ensures that students have strong foundational knowledge before moving into complex constructions.
SECTION B – Construction-Based & Analytical Questions (Any 3 × 7 = 21 Marks)
This section requires deeper problem-solving, formal constructions, grammar conversion, and machine design.
1. DFA Design Problem
Definition of Deterministic Finite Automaton
Design of a DFA accepting binary numbers divisible by 5
2. Recursive Definition & Regular Expression Construction
Given a state transition diagram (Fig. 1 included in the paper), students must derive an equivalent regular expression.
3. Grammar Reduction to CNF
Grammar
S → bA | aB
A → bAA | aS | a
B → aBB | bS | b
must be converted into Chomsky Normal Form (CNF).
4. PDA Construction
Design a Pushdown Automaton for
*L = { w c wᴿ | w ∈ {a,b} }**,
i.e., palindromic structure around a central ‘c’.
5. Turing Machine Construction
Construct a Turing Machine for
L = { aⁿ bⁿ | n > 0 },
which checks equal numbers of a’s and b’s.
These questions test grammar manipulation, automata design, and Turing machine conceptualization.
SECTION C – Higher-Level Theory & Problem Solving (7 Marks Each)
This section presents advanced conceptual, conversion, and proof-based questions.
Q3 – Mealy/Moore Conversion or DFA Minimization
Explanation and examples of Mealy and Moore machines
Conversion of the given Mealy machine (Fig. 2) to a Moore machine
OR
Constructing minimum-state DFA equivalent to the provided DFA (Fig. 3)
Q4 – Pumping Lemma or Closure Properties
Statement of Pumping Lemma for Regular Languages
Using it to prove that L = { aᵖ | p is prime } is not regular
OR
Discussing closure properties of regular languages:
Union
Concatenation
Intersection
Complement
Q5 – Ambiguity or Parse Tree Construction
Discuss inherent ambiguity in CFLs
Construct a CFG for:
L = { aⁱ bʲ cᵏ | i = j OR j = k }
OR
Given productions, construct a parse tree for “abbcde”:
S → a A c B e
A → A b | b
B → d
Determine whether the grammar is ambiguous
Q6 – Deterministic vs Non-Deterministic PDA
Differences between DPDA and NPDA with examples
Discussion of two-stack PDA and its computational power (equivalent to TM)
OR
Construct PDA equivalent to CFG:
S → a A A
A → a S | b S | a
Q7 – Turing Machine Theory & PCP
Short notes on:
Halting Problem
Recursive languages
Variants of Turing Machines
OR
Define Post’s Correspondence Problem (PCP) and Modified PCP
Find three solutions for:
x = (b, bab³, ba)
y = (b³, ba, a)
