Department of Computer Science and Engineering

Question Bank
Subject: Formal Languages and Automata Theory Year & Sem: III - I
Academic Year: 2025-26 Branch & Sec: CSE C&D
Name of the Faculty: Dr. Padavala Sai Prasad Regulation: R23

MID-I
Unit-I

Syllabus:
Finite Automata: Need of Automata theory, Central Concepts of Automata Theory, Automation,
Finite Automation, Transition Systems, Acceptance of a String, DFA, Design of DFAs, NFA, Design
of NFA, Equivalence of DFA and NFA, Conversion of NFA into DFA, Finite Automata with ε -
Tansitions, Minimization of Finite Automata, Finite Automata with output-Mealy and Moore
Machines, Applications and Limitation of Finite Automata.

Textbooks:

Introduction to Automata Theory, Languages and Computation, J. E. Hopcroft, R.Motwani and J. D.

Ullman, 3rd Edition, Pearson, 2008

CO I : Understand the fundamental concepts of formal languages, grammars and automata theory.

Part-A
Short Answer Questions (2M)
Q. No Question BL CO PO
1 List the various operations on languages. I I 1
2 List and explain the classifications of Finite Automata. I I 1, 2
List the various operations on languages in detail and relate
3 I I 1, 3
with transition diagrams.
4 Define Deterministic and Non-deterministic finite automaton. I I 1
5 Demonstrate the mathematical definition of DFA. II I 1
Draw a DFA which accepts strings ending with 11 where the
6 III I 1, 3
input is {0, 1}.

Page | 1
 Explain the formal definition of an NFA with a suitable
7 II I 2
example.
8 What is the importance of ε- Transitions? I I 3
9 Briefly discuss about Finite Automata with Epsilon- Transition. IV I 2, 3
Compare features of NFA and NFA- ε transitions with
10 IV I 3
example.
11 Discuss the applications of Finite Automata. IV I 2
12 List the elements and components of DFA and NFA. I I 2
13 Write the steps for minimizing DFA. I I 1

Part-B
Long Answer Questions (10M)
Q. No Question BL CO PO
List and explain the components of finite state model with
1 II I 1, 2
examples.
Construct a DFA accepting the set of all strings ending with
2 III I 2, 3
‘bb’ over Σ= {a, b}.
Design an NFA- ε to accept the string of a's and b's, such that,
3 it can accept either the string consisting of one a followed by III I 2, 3
any number of a's or one b followed by any number of b's.
Draw the transition diagram of a FA which accepts all strings
4 of 0’s and 1’s in which the number of 0’s are odd and 1’s are III I 2, 3
even.
Convert the given NFA to equivalent DFA.

5 III I 3

Construct DFA equivalent to the given NFA.

6 III I 3

7 Find whether the two DFAs given below are equivalent or not? II I 2, 3

Page | 2
 Construct the minimum state equivalent DFA.

8 III I 2, 3

Construct a Moore machine that determines whether an input

9 string contains an even or odd number of 1's. The machine III I 2, 3
should give 1 as output if an even number of 1's are in the
string and 0 otherwise.
10 Construct the moore machine to determine residue mod 3. III I 3
Compare and contrast Melay and Moore machines. Give an
11 II I 2, 3
example for each.

Unit-II

Syllabus:
Regular Expressions, Regular Sets, Identity Rules, Equivalence of two RE, Manipulations of REs,
Finite Automata and Regular Expressions, Inter Conversion, Equivalence between FA and RE,
Pumping Lemma of Regular Sets, Closure Properties of Regular Sets, Grammars, Classification of
Grammars, Chomsky Hierarchy Theorem, Right and Left Linear Regular Grammars, Equivalence
between RG and FA, Inter Conversion.

Textbooks:

Introduction to Automata Theory, Languages and Computation, J. E. Hopcroft, R.Motwani and J. D.

Ullman, 3rd Edition, Pearson, 2008

CO II : Demonstrate the knowledge of regular expressions for regular language and finite automata.

Page | 3
 Part-A
Short Answer Questions (2M)
Q. No Question BL CO PO
1 Define regular expression. I II 1
2 Explain the operations and properties of regular expressions. II II 1
Construct a NFA equivalent to the regular expression
3 III II 2, 3
(10+11)*00.
4 State pumping lemma for regular languages. I II 1
5 Explain the Chomsky classification of grammars. II II 1
6 Construct the right linear grammar for the language (01)*0. III II 3
Construct the left linear grammar for the language
7 III II 3
(0+1)*00(0+1)*.
8 List and explain the closure properties of Regular grammar. I II 1, 2
9 Simplify the following R.E. r= ε + a*(abb)*(a*(abb)*)*. IV II 2
How to find equivalence of regular grammar and finite
10 I II 2, 3
automata?

Part-B
Long Answer Questions (10M)
Q. No Question BL CO PO
Construct a finite automaton for the regular expression r =
1 III II 2, 3
01*+10, also present its transition table.
Give regular expression for representing the set L of strings in
2 I II 1, 2
which every 0 is immediately followed by at least two 1's.
Draw the DFA for the following Regular Expressions.
3 III II 3
a. (0+1)*101 b. a*b*a
Apply pumping lemma for the language L= {an/n is prime} and
4 II II 1, 2
prove that it is not regular.
Design a ε-NFA for the regular expression a*b+cb*+ac*b.
5 III II 1, 3
Then convert it into a DFA.
With suitable examples, explain about the closure properties of
6 II II 2
regular sets.
7 Write equivalent regular expression for the following DFA. I II 1, 2

Page | 4
 8 Illustrate the Chomsky hierarchy with a neat sketch. II II 3
Explain the procedure for converting finite automata to regular
9 II II 2, 3
grammar with an example.
Explain the step-by-step method to generate equivalent FA for
10 II II 3
the regular expressions of different forms.
11 Explain the Pumping lemma for the regular sets. II II 2

MID-II
Unit-III
Syllabus:
Formal Languages, Context Free Grammar, Lefmost and Rightmost Derivations, Parse Trees,
Ambiguous Grammars, Simplification of Context Free Grammars-Elimination ofUseless Symbols, E-
Productions and Unit Productions, Normal Forms-Chomsky NormalForm and Greibach Normal Form,
Pumping Lemma, Closure Properties, Applications of Context Free Grammars.

Textbooks:

Introduction to Automata Theory, Languages and Computation, J. E. Hopcroft, R.Motwani and J. D.

Ullman, 3rd Edition, Pearson, 2008

CO III : Design context free grammars for formal languages.

Part-A
Short Answer Questions (2M)
Q. No Question BL CO PO
1 Define Context free grammar. I III 1
2 Discuss the applications of Context free grammar. IV III 2
List and explain four components used to form a context free
3 II III 1, 2
grammar.
4 Define ambiguous grammar. I III 1
5 Discuss the simplification of context free grammar. IV III 2
Page | 5
 What is the importance of useless symbols and unit productions
6 I III 1
in Context free grammar?
Eliminate NULL productions for the grammar.
S→ ABC | BaB
A→ Aa | BaC | aaa
7 I III 1, 2
B→ bbb | a | D
C→ CA | AC
d→ ε
With a step wise procedure explain how to reduce a grammar
8 II III 2
into CNF.
Find the GNF equivalent to the following.
1
9 S → AA | 0 I III
A → SS | 1
10 What types of productions are accepted in CFG? I III 2

Part-B
Long Answer Questions (10M)
Q. No Question BL CO PO
1 How to simplify a CFG? Explain with an example. I III 1, 2
Consider the grammar S→ aS | aSbS | ε
Is the above grammar ambiguous?
2 I III 1, 2
Show in particular that the string ‘aab’ has to :
i. parse tree ii. Leftmost derivation iii. Rightmost derivation
For the grammar G = ({S}, {a, b}, S, P), find out the context
free language.
The productions are given below,
3 S → abB I III 1
A → aaBb
A→ε
B → bbAa
4 Show that the language L = {anbn | n≥1} is unambiguous. I III 2
Construct an equivalent unambiguous grammar for the
5 following grammar: III III 1, 2
E→ E+E | E*E | (E) | id
6 Explain the step-by-step method to prove that certain languages II III 2

Page | 6
 were not Regular.
Consider the CFG with {S,A,B) as the non-terminal alphabet,
{a,b) as the terminal alphabet, S as the start symbol and the
following set of production rules
7 S → ASA | aB | b I III 1, 2
A→B
B→b|ε
Find a reduced grammar equivalent to the above grammar.
Eliminate Null, unit and useless production from the following
grammar.
S→ AaA | CA | BaB
8 A→ aaBa | CDA | aa | DC I III 1, 2
B→ bB | bAB | bb | aS
C→ Ca | bC | D
D→ bD | ε
Simplify the following grammar.
S → Aa | B
9 IV III 1, 2
B → A | bb
A → a | bc | B
Write context free grammar for the language.
10 I III 1
L={aibjck | i+j=k, i≥0, j≥0}
Convert the below CFG to CNF:
S → a | aA | B
11 III III 1, 2
A → aBB | ε
B → Aa | b
Convert the following grammar to Greibach Normal Form.
S→ ABA | AB | BA | AA | B
12 III III 1, 2
A→ aA | a
B→ bB | b

Unit-IV
Syllabus:
Pushdown Automata, Definition, Model, Graphical Notation, Instantaneous Description, Language
Acceptance of Pushdown Automata, Design of Pushdown Automata, Deterministic and Non -
Deterministic Pushdown Automata, Equivalence of Pushdown Automata and Context Free Grammars,
Conversion, Two Stack Pushdown Automata, Application of Pushdown Automata.
Page | 7
Textbooks:

Theory of Computer Science-Automata, Languages and Computation, K. L. P. Mishraand N.

Chandrasekharan, 3rd Edition, PHI, 2007

CO IV : Understand the relation between Context free Languages and PDA.

Part-A
Short Answer Questions (2M)
Q. No Question BL CO PO
1 Define Push Down Automata (PDA). I IV 1
2 Discuss about the languages accepted by PDA. IV IV 2
3 Explain the elements of PDA. II IV 2
Show the procedure and explain to find the equivalence of
4 III IV 2, 3
PDA and context free grammar.
5 In what ways a PDA can show the acceptance of a string. II IV 2
6 Demonstrate the conversion of PDA to grammar. II IV 2
7 Discuss the use of NPDA in solving real-world problems. IV IV 2
Does push down automata have memory? Justify your
8 V IV 2
answer.
9 Mention the applications of PDA. I IV 1
Show that {ambncp| m < n or n < p} is not deterministically
10 I IV 2
context-free.
11 Compare features of NFA and NFA-€ transitions with example. II IV 2, 3

Part-B
Long Answer Questions (10M)
Q. No Question BL CO PO
What is an Instantaneous Description? Give the general model
1 I IV 1, 3
and graphical representation of a PDA.
2 Construct PDA for L = {0n1m2k)} Where n,m,k>=1. III IV 3
Demonstrate the conversion of PDA to grammar with a case
3 II IV 3
study.
4 Design Push Down Automata for L = {a2nbn | n ≥ 1}. III IV 3
5 Construct a deterministic PDA accepting L = {w ϵ {a, b} * | the III IV 2, 3

Page | 8
 number of a's in w equals the number of b's in w} by final state.
Convert the following Context Free Grammar to Push Down
Automata.
6 S→ aA | bB III IV 1, 2
A→ aB | a
B→ b
Convert the following grammar to PDA that accepts the same
7 III IV 1, 2
language by empty stack S→ 0AA, A→ 0S / 1S / 0.
Construct the equivalent grammar for the PDA.
M=({q0,q1}, {0,1}, {R,Z0}, δ, q0, Z0, Φ ) and δ is given by
δ(q0,0,Z0)=(q0,RZ0)
δ(q0,0,R)=(q0,RR)
8 III IV 2, 3
δ(q0,1,R)=(q1,R)
δ(q1,1,R)=(q1,R)
δ(q1,0,R)=(q1,ε)
δ(q1,ε,Z0)=(q1,ε)
Write about top-down parsing and bottom-up parsing using
9 I IV 1, 2
PDAs.
10 Demonstrate the importance of PDA using a case study. II IV 3
Compare the features of DPDA (Deterministic Push Down
11 Automata) and NPDA (Non Deterministic Push Down II IV 2, 3
Automata) with a suitable example.
With an example, explain the structure and working of tow-
12 II IV 1, 2
stack PDA.

Unit-V
Syllabus:
Turning Machine: Definition, Model, Representation of TMs-Instantaneous Descriptions,Transition
Tables and Transition Diagrams, Language of a TM, Design of TMS, Types ofTMs, Church's Thesis,
Universal and Restricted TM, Decidable and Un-decidable Problems,Halting Problem of TMs, Post's
Correspondence Problem, Modified PCP, Classes of P andNP, NP-Hard and NP-Complete Problems.

Textbooks:

Theory of Computer Science-Automata, Languages and Computation, K. L. P. Mishraand N.

Chandrasekharan, 3rd Edition, PHI, 2007

CO V : Distinguish between decidability and undecidability.

Page | 9
 Part-A
Short Answer Questions (2M)
Q. No Question BL CO PO
1 Define a Turing Machine. I V 1
2 What are the components of Turing Machine? I V 1
3 What is id of a Turing Machine? I V 1
4 List the elements of TM’s and give the block diagram of TM. I V 1, 3
5 Write about halting problem in Turing machines. I V 2
6 What is meant by Turing Reducibility? I V 1
7 Briefly explain about post's correspondence problem. II V 1, 2
8 Write a short note on Church’s hypothesis. I V 2
9 Write a short note on linear bounded automata. I V 2
Discuss the decidable and undecidable problems with
10 IV V 2
examples.
11 What is the Turing test and why is it important? I V 1, 2
What is meant by Reducibility in NP-problems and why it is
12 I V 1, 2
required? Explain.

Part-B
Long Answer Questions (10M)
Q. No Question BL CO PO
1 Discuss the languages accepted by Turing machines. IV V 2
2 Construct a TM for computing ones complement calculation. III V 3
Construct a TM that computes a function f(m, n) = m+n i.e,
3 III V 1, 3
addition of two numbers.
4 Design a Turing Machine to accept L={WWR | W is in (a+b)*}. III V 3
Design a Turing machine to recognize the language {1n2n3n |
5 III V 3
n≥1}.
List and briefly explain different variants in Turing Machines.
6 I V 1, 2
Explain the concept of Universal Turing Machine.
Define the terms:
7 (i) Turing Semi-Decidable (ii) Turing Undecidable I V 1
(iii) Reducibility
Describe various ways of representing Turing machines with
8 II V 2, 3
suitable examples.
Page | 10
 Check whether the following post correspondence problem has
a solution or not.
9 I V 2, 3

10 What are the circumstances under P = NP and P ≠ NP? I V 1, 2

11 Write short note on NP- hard and NP- complete problem. I V 1
Show that the Post Correspondence Problem is decidable over
12 I V 2
unary alphabet.

Page | 11