Course Name: Course code:R2331053
Year/sem: III BTECH I SEM Regulation:R23
Course Coordinator: Ms.P GANGA BHAVANI SEC:C
Academic Year: 2025-2026
Formal Languages and Automata Theory (CSE 3-1)
Assignment 1
Course Outcome (CO1)
Question BT Relevance to
Questions Marks
No. Level PO's and PSO's
A) Explain the need for Automata Theory in computer science.
1 K3 PO3, PSO2 10
Describe its significance and applications with examples.
B) Discuss the central concepts of Automata Theory, including
automata, states, alphabets, languages, and acceptance of K2 PO1, PSO1
strings.
A) What is a Non-deterministic Finite Automaton (NFA)?
2 K2 PO2, PSO1 10
Explain its working and structure with an example.
B) Design an NFA for the language defined by the regular
expression (a + b)abb and explain how it accepts strings of the K3 PO2, PSO1
language prove that with the acceptance of a string.
A) Explain the equivalence of DFA and NFA. Why are both
3 K3 PO3, PSO2 10
models important?
B) Describe the conversion of an NFA into an equivalent DFA
using the subset construction method. Illustrate with an K3 PO2, PSO1
example of Transition System
UNIT 2 Assignment 2
Course Outcome (CO2)
Question BT Relevance to PO's
Questions Marks
No. Level and PSO's
A) Define Regular Expressions and discuss their
1 K2 PO2, PSO1 10
properties and identity rules with examples.
B) Explain the equivalence of two regular expressions.
K3 PO3, PSO2
Demonstrate with suitable examples.
A) Explain the inter-conversion between Finite Automata
2 K3 PO3, PSO2 10
and Regular Expressions with examples.
B) Describe the Pumping Lemma for Regular Sets and
K3 PO3, PSO2
illustrate its use to prove a language is not regular.
A) Discuss the Closure Properties of Regular Sets with
3 K2 PO1, PSO1 10
examples.
B) Explain the Chomsky Hierarchy and classify grammars
K3 PO3, PSO2
with examples for each type.
Assignment 3
Course Outcome (CO3 & CO4)
UNIT 3
Question BT Relevance to PO's
Questions Marks
No. Level and PSO's
A) Define Context-Free Grammar (CFG) and explain the
1 concepts of leftmost and rightmost derivations with K2 PO2, PSO1 10
examples.
B) Discuss ambiguous grammars and show an example of
K3 PO3, PSO2
an ambiguous grammar.
A) Explain the simplification of CFGs including elimination
2 K3 PO3, PSO2 10
of useless symbols, ε-productions, and unit productions.
B) Define Chomsky Normal Form and Greibach Normal
K3 PO3, PSO2
Form. Explain their importance with examples.
A) State and explain the Pumping Lemma for Context-Free
3 K3 PO3, PSO2 10
Languages with an example.
B) Describe applications of Context-Free Grammars in
K2 PO1, PSO1
computer science.
Assignment 4
Course Outcome (CO5)
UNIT 4
Question BT Relevance to PO's
Questions Marks
No. Level and PSO's
A) Define Pushdown Automata (PDA). Explain the model
1 K2 PO2, PSO1 10
and graphical notation with an example.
B) Explain the language acceptance by PDA and provide
K3 PO3, PSO2
an example PDA accepting a simple language.
A) Differentiate between Deterministic and Non-
2 K2 PO1, PSO1 10
deterministic PDA with examples.
B) Explain the equivalence between PDA and Context-
K3 PO3, PSO2
Free Grammars (CFGs) with an example.
A) Describe the concept of Two Stack PDA and its
3 K2 PO1, PSO1 10
significance.
B) Discuss applications of Pushdown Automata in
K2 PO1, PSO1
computer science.
Assignment 5
Course Outcome (CO6)
UNIT 5
Question BT Relevance to PO's
Questions Marks
No. Level and PSO's
A) Define Turing Machine (TM). Explain its components
1 K2 PO2, PSO1 10
and representation with an example.
B) Describe instantaneous descriptions, transition tables,
K3 PO3, PSO2
and transition diagrams of a TM.
A) Explain the language of a Turing Machine and discuss
2 K3 PO3, PSO2 10
types of TMs with examples.
B) Describe Church’s Thesis and its significance in
K2 PO1, PSO1
computability theory.
A) Discuss Undecidable Problems with examples
3 K3 PO3, PSO2 10
including the Halting Problem.
B) Explain NP-Hard and NP-Complete problems with
K3 PO3, PSO2
examples.
