This document is a B.Tech Semester IV Theory Examination Question Paper for the subject BCS402 – Theory of Automata and Formal Languages, from the academic session 2023–2024. It is a 3-hour, 70-mark paper designed to check a student's conceptual and analytical understanding of automata theory, grammars, and computational models.
The question paper is organized into three major sections:
SECTION A – Basic & Short Questions
SECTION B – Intermediate & Construction-Based Questions
SECTION C – Advanced Theory, CFG/PDA/TM Problems
Each section tests different levels of understanding—from definitions to designing automata and deep grammar transformations.
SECTION A (14 Marks – 7 Questions × 2 Marks)
This section contains short, introductory questions checking theoretical basics:
Mathematical definition of DFA and difference between DFA vs NFA
DFA construction for strings ending with 101
Regular expressions for strings with two consecutive 0s and 1s
Language generation from a given CFG
Leftmost derivation from a grammar
Concept and example of two-stack PDA
Explanation of Multi-Tape Turing Machine
These questions validate fundamental knowledge of formal languages and automata.
SECTION B (21 Marks – Attempt Any 3)
This section includes construction-based and explanation-oriented questions such as:
DFA for binary numbers divisible by 4
Regular expression using Arden’s Theorem (with a diagram provided on Page 1)
Converting a right-linear grammar to left-linear grammar
Difference between DPDA and NPDA, including PDA construction for aⁿbⁿ
Deterministic vs Non-deterministic Turing Machines, plus TM design for ww
This section tests design skills, grammar transformations, and understanding of computational models.
SECTION C (28 Marks – Attempt 1 From Each)
This section contains deep theoretical, constructive, and derivation-focused problems.
3. Automata Constructions
Construct DFA from NFA with epsilon transitions
Minimize a given DFA diagram
4. Regular Language Properties
Apply Pumping Lemma to show L = {aᵖ | p is prime} is not regular
Discuss closure properties of regular languages
5. Context-Free Grammars (CFG)
Convert grammar to Chomsky Normal Form (CNF)
Construct CFG for languages such as:
L = {0ᵐ1ⁿ | m ≠ n}
L = {aᵖbᵖcʳ | p + q = r}
6. PDA & Grammar Conversion
Construct PDA equivalent to a given CFG
Convert PDA to CFG using formal transformations
7. Turing Machine & Theory of Computation
Construct Turing Machine accepting L = {a²ⁿbⁿ} and show instantaneous description
Short theoretical notes on:
Universal Turing Machine
Post Correspondence Problem
Recursive & Recursively Enumerable Languages
These questions check the student’s mastery over deeper computational theory concepts and their application.
Overall Purpose of the Document
This exam paper evaluates a student's ability to:
Define and differentiate various computational models
Construct automata such as DFA, NFA, PDA, and Turing Machines
Convert and manipulate regular expressions, CFGs, and PDAs
Apply theoretical tools like Pumping Lemma, grammar transformations, and state minimization
Understand the hierarchy of formal languages and their properties
The document combines theoretical, numerical, and construction-based problems to ensure a comprehensive assessment of Automata Theory and Formal Languages.
