THEORY OF AUTOMATA & FORMAL LANGUAGES — B.Tech (SEM-IV), RCS-403
This is a 3-hour, 70-mark theory examination designed to evaluate students’ understanding of:
Formal languages Finite automata
Regular expressions Context-free grammars
Pushdown automata Turing machines
Closure properties Non-regular and non-context-free proofs
The paper is divided into three sections—testing conceptual clarity, construction-based questions, derivations, and machine designs.
SECTION A — Short Conceptual Questions (2 × 7 = 14 Marks)
This section contains seven brief questions, covering key foundational concepts.
Topics include:
Computing result of language operations over L₁, L₂, L₃ Designing FA for strings ending with 101
Regular expression for “number of a’s divisible by 3” CFG construction for L = {a²ⁿ bⁿ | n ≥ 3}
ε-closure in FA
Universal Turing Machine Two-stack Pushdown Automaton
These assess definitions, small constructions, and language operations.
SECTION B — Descriptive & Construction Questions (7 × 3 = 21 Marks)
Attempt any 3 out of 5 questions.
This section examines your ability to convert and construct automata/grammars.
Topics include:
Minimization of a given FA Regular expression from the given automaton
Converting CFG to Greibach Normal Form (GNF) PDA for L = { aᶦ bʲ cᵏ | i = j OR j = k }
Turing Machine for L = { aⁿ⁺² bⁿ | n > 0 }
This section checks machine design skills, grammar transformations, and RE/FA conversions.
SECTION C — Advanced Theoretical / Machine Design Questions (7 marks each)
Each question has choice (a or b).
This section requires higher-level reasoning, proofs, PDA/TM design, and CFG construction.
Q3 – Finite Automata / Myhill–Nerode
FA for ternary numbers divisible by 5
Myhill–Nerode Theorem explanation with example
Q4 – Regular Languages & Closure
Proving L = {aⁿ bⁿ} is not regular
Closure properties of regular languages
Q5 – Context-Free Grammars & CFL Proofs
CFG for:
L = {0ᵐ 1ⁿ | m ≠ n, m,n ≥ 1}
L = {aˡ bᵐ cⁿ | l + m = n}
Proving L = {aⁿ bⁿ cⁿ} is not context-free
Q6 – Pushdown Automata & CFG Generation
PDA for L = { W Wᴿ | W ∈ {a,b}* } (palindromes)
Constructing CFG from a given PDA transition table
Q7 – Turing Machines & Undecidability Concepts
TM for L = { aⁿ bⁿ cⁿ | n ≥ 1 }
Short notes on:
Recursive & Recursively Enumerable Languages
PCP & Modified PCP Problems
This section evaluates advance-level understanding of formal languages and computational models.
OVERALL PURPOSE OF THE EXAM
This question paper checks whether the student can:
Perform language operations and write regular expressions
Convert FA ↔ RE ↔ DFA ↔ minimized DFA
Construct CFGs, PDAs, and TMs
Apply Myhill–Nerode theorem
Prove languages non-regular or non-CFL
Understand normal forms (GNF)
Design Turing machines for multi-condition languages
Understand decidability & classical computation problems
It ensures strong foundational knowledge in theory of computation, essential for compiler design, algorithm theory, machine learning foundations, and advanced CS.
