(SEM IV) THEORY EXAMINATION 2018-19 THEORY OF AUTOMATA AND FORMAL LANGUAGES

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.