(SEM IV) THEORY EXAMINATION 2023-24 THEORY OF AUTOMATA AND FORMAL LANGUAGES

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.