(SEM IV) THEORY EXAMINATION 2017-18 THEORY OF AUTOMATA AND FORMAL LANGUAGES

The B.Tech Theory of Automata & Formal Languages (RCS403) question paper from the 2017–18 IV Semester Theory Examination is a comprehensive and analytically oriented 70-mark exam. It evaluates a student’s command over automata theory, formal languages, grammars, Turing machines, closure properties, ambiguity, and computational models. Spread across three extensive sections, the paper demands conceptual clarity, language construction skills, machine design ability, conversions, reductions, and theoretical proofs.

SECTION A – Foundational Concepts (Short Answer Questions, 14 Marks)

This section contains seven 2-mark questions covering essential definitions, basic constructions, and introductory-level automata operations.

Topics include:

Definitions of alphabet, string, and language

Designing a regular expression over {a, b} containing exactly two a’s

Designing an NFA accepting strings containing substring “abba”

Definition of Chomsky Hierarchy

Closure of context-free languages under union (with example)

Converting a given NFA to DFA

Removing useless productions from a provided grammar

This section ensures that students have strong foundational knowledge before moving into complex constructions.

SECTION B – Construction-Based & Analytical Questions (Any 3 × 7 = 21 Marks)

This section requires deeper problem-solving, formal constructions, grammar conversion, and machine design.

1. DFA Design Problem

Definition of Deterministic Finite Automaton

Design of a DFA accepting binary numbers divisible by 5

2. Recursive Definition & Regular Expression Construction

Given a state transition diagram (Fig. 1 included in the paper), students must derive an equivalent regular expression.

3. Grammar Reduction to CNF

Grammar

S → bA | aB   A → bAA | aS | a   B → aBB | bS | b  

must be converted into Chomsky Normal Form (CNF).

4. PDA Construction

Design a Pushdown Automaton for
*L = { w c wᴿ | w ∈ {a,b} }**,
i.e., palindromic structure around a central ‘c’.

5. Turing Machine Construction

Construct a Turing Machine for
L = { aⁿ bⁿ | n > 0 },
which checks equal numbers of a’s and b’s.

These questions test grammar manipulation, automata design, and Turing machine conceptualization.

SECTION C – Higher-Level Theory & Problem Solving (7 Marks Each)

This section presents advanced conceptual, conversion, and proof-based questions.

Q3 – Mealy/Moore Conversion or DFA Minimization

Explanation and examples of Mealy and Moore machines

Conversion of the given Mealy machine (Fig. 2) to a Moore machine
OR

Constructing minimum-state DFA equivalent to the provided DFA (Fig. 3)

Q4 – Pumping Lemma or Closure Properties

Statement of Pumping Lemma for Regular Languages

Using it to prove that L = { aᵖ | p is prime } is not regular
OR

Discussing closure properties of regular languages:

Union

Concatenation

Intersection

Complement

Q5 – Ambiguity or Parse Tree Construction

Discuss inherent ambiguity in CFLs

Construct a CFG for:
L = { aⁱ bʲ cᵏ | i = j OR j = k }
OR

Given productions, construct a parse tree for “abbcde”:

S → a A c B e   A → A b | b   B → d 

Determine whether the grammar is ambiguous

Q6 – Deterministic vs Non-Deterministic PDA

Differences between DPDA and NPDA with examples

Discussion of two-stack PDA and its computational power (equivalent to TM)
OR

Construct PDA equivalent to CFG:

S → a A A   A → a S | b S | a  

Q7 – Turing Machine Theory & PCP

Short notes on:

Halting Problem

Recursive languages

Variants of Turing Machines
OR

Define Post’s Correspondence Problem (PCP) and Modified PCP

Find three solutions for:

x = (b, bab³, ba)

y = (b³, ba, a)