This document contains the complete B.Tech (Semester IV) Theory Examination 2024–25 question paper for Theory of Automata and Formal Languages (BCS402). The paper spans four printed pages, carries 70 marks, and evaluates a student’s understanding of automata theory, formal grammars, Turing machines, PDA design, regular expressions, NFA–DFA conversion, and decidability concepts.
Section A – Short Conceptual Questions (14 Marks)
Section A contains seven 2-mark questions, each testing basic theoretical concepts:
Definition of Alphabet in automata (Page 1)
Difference between DFA and NFA
Writing a regular expression for strings ending with 01
Understanding ambiguity in CFGs
Constructing a CFG for L = {aⁿbⁿ}
Checking whether grammar S → S*S | S+S | a is ambiguous
Designing a Turing Machine for language L = {aⁿbⁿ | n ≥ 1}
These questions evaluate foundational knowledge of formal languages, grammars, and computation.
Section B – Medium-Length Analytical Questions (21 Marks)
Students must attempt any three out of five questions, covering NFA → DFA conversion, Arden’s theorem, grammar-to-FA conversion, PDA design, and unary Turing machine arithmetic:
Includes (Page 2):
Proving equivalence of NFA and DFA using subset construction
Finding regular expression using Arden’s Theorem for a given transition diagram
Converting a regular grammar into a finite automaton
Designing a PDA for L = {wwᴿ}, i.e., palindrome recognition
Designing a Turing Machine to compute f(n) = n + 1 for unary inputs
This section checks analytical thinking and construction-based problem-solving.
Section C – Long, Advanced Construction & Proof Questions (35 Marks)
Q3 – NFA to DFA / DFA Minimization (Page 3)
Construction of a DFA corresponding to the given NFA (figure shown)
OR finding the minimum state automaton equivalent to a given DFA (diagram on page)
Q4 – Pumping Lemma / Arden’s Theorem
Proving L = {aⁿbⁿcⁿ} is not regular
OR proving (a + b)* a (a + b)* is regular using Arden’s theorem
Q5 – CNF Conversion / Ambiguity Testing
Converting CFG S → aSB | ε to Chomsky Normal Form
OR checking ambiguity of grammar S → aSb | ε using derivation trees
Q6 – CFG Simplification / PDA for Palindromes
Simplifying CFG S → AbaC … (Page 3)
OR designing a PDA for palindromes over {a, b}*
Q7 – Universal Turing Machine / PCP
Explaining Universal Turing Machine and designing TM for f(n) = 2n
OR discussing Post’s Correspondence Problem and its undecidability
These questions evaluate deep understanding of computation theory, decidability, automata construction, and formal grammar transformations.
Summary
The Theory of Automata and Formal Languages (BCS402) exam paper comprehensively covers:
Deterministic & Non-Deterministic Automata
Regular Expressions & Regular Grammars
Context-Free Grammars & Ambiguity
PDA construction & palindrome recognition
Turing Machines, unary arithmetic, Universal TM
NFA–DFA conversion & DFA minimization
Arden’s theorem & pumping lemma
CNF conversion & CFG simplification
PCP and undecidability concepts
It serves as an excellent academic resource for students studying the foundations of computation and formal language theory.
