UNIT-I

PART-A

Bloom's
S.No. Coverage Questions Marks
Level
1 UNIT-I (a) Define NFA with example? [1M] L2
2 UNIT-I (b) What is Finite Automata with ε -Move. [1M] L1

3 UNIT-I (c) Explain any finite automata with output? [1M] L2

4 UNIT-I (d) Applications of FA? [1M] L3

5 UNIT-I (e) Define DFA with example? [1M] L2

6 UNIT-I (f)what is Kleene closure Language? [1M] L1
7 UNIT-I (g)Describe Mealy machine? [1M] L2
8 UNIT-I (h)Describe Moore machine? [1M] L2
9 UNIT-I (i) Explain any finite automata without output? [1M] L2
10 UNIT-I (j) Write different types of Automata? [1M] L1

PART-B
Bloom's
S.No. Coverage Questions Marks
Level
1 UNIT-I a) Consider the below finite automata and [5M] L3

check the strings are accepted or not

(i) 1110 (ii) 0001 (iii) 1010

b) Define NFA. What are the differences between [5M] L2

DFA & NFA
2 UNIT-I a) Define Grammar. What are the [5M] L2
tuples?

b) Convert NFA to DFA

[5M] L4
3 UNIT-I a) Convert NFA to DFA [5M] L2

[5M] L2

b) Explain briefly about DFA and NFA?

4 UNIT-I a) Convert NFA to DFA [5M] L2

b) Obtain a DFA to accept strings of a’s and b’s [5M]
L4

having even number of a’s and b’s

5 UNIT-I a) Obtain a DFA to accept strings of a’s [5M] L4

and b’s starting with the string ab. [5M]
b) Convert NFA to DFA L2

6 UNIT-I A) Convert the following NFA with ε moves to [10M] L2

DFA without ε moves.

7 UNIT-I a) Obtain DFAs to accept strings of a’s [5M] L4

and b’s having exactly one a
 b) Explain in detail about NFA and DFA. [2.5M]
c) Explain in detail about mealay and moore. [2.5M] L2
8 UNIT-I Convert the following NFA with ε moves to [10M] L2
DFA

9 UNIT-I Minimize the following finite automata. [10M] L3

10 UNIT-I [10M] L2
Define Moore machine? Construct Mealy

machine corresponding to Moore machine?

UNIT-II

PART-A
 Bloom's
S.No. Coverage Questions Marks
Level
1 UNIT-II Draw Series FA with Episilon Moves. [1M] L1
2 UNIT-II Draw Parallel FA with Episilon Moves. [1M] L5
3 UNIT-II Draw Kleen Closure FA with Episilon Moves. [1M] L1

4 UNIT-II Write Arden’s Theorem [1M] L1

5 UNIT-II Write Closure Properties of Regular Languages [1M] L5

6 UNIT-II Write Decision Properties of Regular Languages [1M] L1

7 UNIT-II Write Applications of Pumping Lemma [1M] L1
8 UNIT-II Draw Series FA without Episilon Moves. [1M] L1
9 UNIT-II Draw Parallel FA without Episilon Moves. [1M] L1
10 UNIT-II Draw Kleen Closure FA without Episilon Moves. [1M] L1

PART-B
Bloom's
S.No. Coverage Questions Marks
Level
1 UNIT-II Convert the following DFA to Regular [10M] L3
Expression

2 UNIT-II [10M] L6
Convert RE 1(0+1)*0 into equivalent DFA

3 UNIT-II (a) List out the identities of Regular [5M] L5

expression. [5M]
 (b) Write the process of equivalence two FA’s?
Find whether the equivalence two FA’s or
not

4 UNIT-II a) Construct an equivalent FA for the given [5M] L3

regular expression (0+1)*(00+11)(0+1)* [5M]
b) List out the identities of Regular expression

5 UNIT-II Construct an equivalent FA for the given [10M] L1

regular expression (a+b)*(ab+ba)(b+a)*

6 UNIT-II Convert FA to Regular Expression [10M] L3

7 UNIT-II Consider Two Different Automaton shown [10M] L5

below in Figure 1.

8 UNIT-II a) Construct an equivalent FA(with and without [10M] L5

episilon movies) for given Regular Expression
1 (0 + 1)* 0
b) Convert FA to Regular Expression
 9 UNIT-II a) Explain in detail about Pumping lemma and Regular [10M] L5
Language.
b) Construct an equivalent FA(with and without
episilon movies) for given Regular Expression
1 (0 + 1)* 0
10 UNIT-II a) Explain the algebraic laws of regular expressions [10M] L3
b) Convert FA to Regular Expression

UNIT-III
PART-A

Bloom's
S.No. Coverage Questions Marks
Level
1 UNIT-III Define Ambiguous grammar [1M] L1

2 UNIT-III Define Left recursion [1M] L1

3 UNIT-III Define Left factoring [1M] L1

4 UNIT-III Applications of CFG [1M] L5

5 UNIT-III How do we show the acceptance of CFL [1M] L1

6 UNIT-III Define Instantaneous description (ID) in PDA. [1M] L1

7 UNIT-III Define CFG? [1M] L1
8 UNIT-III What are Productions in CFG? [1M] L1
9 UNIT-III Define PDA [1M] L5
10 UNIT-III What is a Parse tree? [1M] L5

PART-B
Bloom's
S.No. Coverage Questions Marks
Level
1 UNIT-III Write the procedure and Eliminate left [10M] L5
recursion from the following Grammar
EE+T/T
TT*F/F
F(E)/id
2 UNIT-III a) Write CFG for Palindrome. [10M] L2
b) Solve the string “bbaabb” for the given
Production rules S->ss/bsb/a/b
3 UNIT-III Explain about derivation and parse trees? [10M] L5
Construct the string 0100110 from the
Leftmost and Rightmost derivation.

S0S/1AA

A0/1A/0B

B1/0BB
4 UNIT-III a) Define Ambiguous grammar [5M] L2
b) Remove Left recursion from the grammar [5M]
SSab/T
 TTcd/F
FFa/G

5 UNIT-III (a) Explain Left recursion and Left factoring [5M] L3

(b) Perform left factor from the grammar [5M]
AabB/aB/cdg/cdeB/cdfB
6 UNIT-III [5M] L1
Construct a CFG equivalent to the following [5M]
PDA. δ(q0,a,z0)→(q0,z1z0)δ(q0,a,z0)→(q0,z1z0)

δ(q0,a,z1)→(q0,z1z1)δ(q0,a,z1)→(q0,z1z1)

δ(q0,b,z1)→(q1,λ)δ(q0,b,z1)→(q1,λ)

δ(q1,b,z1)→(q1,λ)δ(q1,b,z1)→(q1,λ)

δ(q1,b,z0)→(q1,z2z0)δ(q1,b,z0)→(q1,z2z0)

δ(q1,c,z2)→(q2,λ)δ(q1,c,z2)→(q2,λ)

δ(q2,λ,z0)→(q2,λ)

7 UNIT-III Define derivation , types of derivation , Derivation [10M] L5

tree & ambiguous grammar. Give example for
each.

8 UNIT-III Create a PDA for the provided CFG, and check if [5M] L5
0104 is supported by it. [5M]
S → 0BB
B → 0S | 1S | 0

9 UNIT-III (a) Define Instantaneous description (ID) in [5M] L3

PDA. [5M]
(b) Explain about the graphical notation of
PDA
10 UNIT-III Construct a CFG equivalent to the [10M] L3
following PDA.
PDA={(p, q), (0, 1), δ, p, q, (Z, X)}, where
p is initial state, q is final state.
δ is defined as δ(p,0,Z)=(p,XZ),
δ(p,0,X)=(p,XX), δ(p,1,X)=(q,ϵ),
δ(p,1,X)=(p,ϵ), δ(p,ϵ,Z)=(p,ϵ).