GITA AUTONOMOUS COLLEGE, BBSR

(Affiliated to BPUT, Odisha)

Question Bank
B. Tech
Branch-CSE
Subject: Formal Language and Automata Theory

Part – I Module BL CO PO
Short Answer Type Questions
1 Define DFA. 1 1 1 1
2 Define Arden’s Theorem. 2 1 2 1
Define and difference between ε – NFA & NFA 1 1 1
3 1
with suitable example.
4 Define Kleene Closure Operation with example. 1 1 1 1
5 Design a DFA for the language L= {000,111} 1 3 1 3
Design a ε – NFA for regular expression a*b* 3 1 3
6 1
over the alphabet {a,b}.
7 Define ε – Closure of a state. 1 1 1 1
Construct a NFA for the language L= {x is a 3 1 3
8 string starts with a and ends with b}, over the 1
alphabet set {a,b}
Find the ε – closure of all the states,

9 1 2 1 1

Design a DFA for the language L= {x| x is a

10 1 2 1 1
string that ends with bb}
11 If NFA has n number of states then find maximum 2 1 2 1
number of states equivalent to DFA.
Check whether the following language is regular
12 or not- 2 2 2 1
L={anbn| n>=1}
13 Write the closure properties of CFL. 3 2 3 1

14 State the Pumping Lemma for CFL 4 1 4 1

15 Define ambiguity in CFG. 3 2 3 1
Consider the grammar-
S → bB |aA
16 3 2 3 1
A → b |bS |aAA
B → a |aS |bBB
 For the string w = bbaababa, find-
1. Leftmost derivation
2. Rightmost derivation
3. Parse Tree

17 Define (P+Q) * 3 2 3 1

Define and differentiate between PDA and

18 TM. 4 1 4 1

19 State the Pumping Lemma for regular language 2 1 2 1

20 Define Lc when L={ab,ba,aaa},alphabet set={a,b} 1 2 1 1

What is trap state in DFA, why it is needed 1 1 1

21 explain with example. 1

22 Define Transducer In TM. 1 2 1 1

23 Differentiate between NFA and DFA with 1 2 1 1
reference to same language.
24 If the length of the string in moore machine is N 1 2 1 1
then find the length of the output string in mealy
machine.
25 Write the Regular Expression of all Strings end 2 1 2 1
with ab over the input symbol {a, b}.

Find out the grammar correspondence to this

26 language(L)= {an | n>=1} 3 1 3 1

Consider the finite automata transition table

shown below with initial and final state = q0

States Inputs
27 1 3 1 1
0 1

q0 q2 q1
q1 q3 q0
 q2 q0 q3
q3 q1 q2

Find the language accepted by the finite

automata.
28 State the definition of Pushdown automata. 4 1 4 1
29 State the definition of Turing machine. 4 1 4 1
30 What is CFL explain with example. 4 1 4 1
31 What is Chomsky normal form? 3 1 3 1
32 State Arden’s Theorem. 4 1 4 1
33 What is universal TM. 4 1 4 1
34 Define Ackermann Function. 5 1 5 1
35 Give two examples of undecidable problem. 5 1 5 1
36 Differentiate the + closure and * closure 1 1 1 1
37 What is the difference between P and NP? 5 1 5 1
38 Give two example of NP complete problems. 5 1 5 1
39 Give two examples of NP hard algorithms. 5 1 5 1
40 State Church-Turing hypothesis. 5 1 5 1
Differentiate between Recursive enumerable set 1 5 1
41 5
and Recursive language
Differentiate between Deterministic TM and non- 4 1 4 1
42
Deterministic TM.
43 What is GNF? 3 1 3 1
44 Define ID for PDA. 4 1 4 1
45 Define Post Correspondence Problem. 5 1 5 1
46 What is nullable symbol in a grammar. 3 1 3 1
47 What is unit production. 3 1 1
48 Who are useless symbols in a grammar, explain 3 1 3 1
with example.
49 Design DFA which accept odd number of “a” 1 1 1 1
and odd number of “b” over the input symbol
{a, b }.
50 List the closure properties of context free 2 1 2 1
Language.
Define Extended Transition Function with
51 example. 2 2 2 1
Part – II Module BL CO PO
Focussed – Short answer type Questions
Design a DFA for the language L= {x| x is a 3 1 3
1. string starts with a only}, over the alphabet set 1
{a,b}.
Design a PDA for the language L= {an. bn | 3 1 3
2. n>=1} 1

Construct a DFA equivalent to given NFA.

3. 1 3 1 3
 Find the ε – NFA for regular expression 0(0* + 2 2 2
4. 2
1)1*.
Draw a DFA over the alphabet set {0,1} which
5. accepts all strings of length 2 and then convert it 1 3 1 3
into equivalent NFA.
Convert the following Mealy machine into equivalent 2 2 2
6. Moore machine. 2

Using CYK algorithm check heather a string “abbb”is a 3 2 3

7. 2
valid member of following CFG.
S𝑆 → 𝐴𝐵
A→ 𝐵𝐵/𝑎, 𝐵 → 𝐴𝐵/𝑏

Convert the following CFG to its equivalent CNF. 2 2 2 1

8.
𝑆 → 𝑏𝐴/𝑎𝐵
𝐴 → 𝑏𝐴𝐴/𝑎𝑆/a
𝐵 → 𝑎𝐵𝐵/𝑏𝑆/b
Convert the following NFA to its equivalent DFA. 2 3 2 3
9.

10 Define and describe all the properties of CFL. 2 1 2 3

Check whether the following language is regular 2 2 1
11 or not- 2
L= {anbn | n>=1}
Eliminate all the Unit production from the following 2 3 1
12 CFG. 3
𝑆 → 𝐴𝑎𝐵|𝐵
𝐵 → 𝐴|𝑏𝑏
𝐴 → 𝑎|𝑏𝑐|𝐵
Check for the ambiguous for the derivation a+b*c for the
grammar
13 E→ E+E 3 2 3 2
E → E*E
E→I
I → a|b|c
Remove the useless production from the following CFG.
14 𝑆 → 𝐴𝐵|𝐴𝐶
𝐴 → 𝑎𝐴𝑏|𝑏𝐴𝑎|𝑎
3 2 3 2
𝐵 → 𝑏𝑏𝐴|𝑎𝑎𝐵|𝐴𝐵
𝐶 → 𝑎𝑏𝐶𝐴|𝑎𝐷𝑏
𝐷 → 𝑏𝐷|aC

15 Convert the following NFA with epsilon to 4 1 4 2

equivalent DFA
 Design a Turing Machine for language L=
16 4 3 4 3
{𝑎𝑛 𝑏𝑛 |𝑛 ≥ 1}
17 Design and explain the working principle of PDA. 1 1 1 1
Check that the string “aabb” is
18 ambigious for following CFG 3 2 3 2
𝑆 → 𝑎𝑆𝑏/𝑆𝑆/ℇ

19 Design a PDA for L= {w| wcwr , w belongs to 4 3 4 3

(a,b)* }
Compute A (1,1) by using Ackermann’s function.
20 5 2 5 2
Constract a PDA that accepts even
21 4 3 4 3
palindromes of the form
L={WWR|W=(a+b) *}
Design the PDA for the following language
22 4 3 4 3
L= {am.bn.cp.dq | m=p,n=q and m,n,p,q>=0}
Design the PDA for the following language
23 4 3 4 3
L={an.b2n| n>=0}
 24 What is left and right recursive grammar? 3 2 3 2

Let G be the grammar

S→ aB|bA
25 A→ a|aS|bAA 3 2 3 2
B→ b|bS|aBB
for the string baaabbabba. Find leftmost derivation,
rightmost derivation and parse tree.
26 Construct the regular expression for the given 4 2 4 2
DFA by using Arden’s Theorem.

Find the context free languages for the following

grammars.
S→ aSbS|bSaS| ε
27 S→ aSb|aAb 4 2 4 2
A→ bAa,
A→ ba

Find the PDA equivalent to the given CFG with

the following productions
28 S→ A, A→ BC, B→ ba, C→ ac 4 2 4 2
S→ aSb|A, A→ bSa|S| ε

29 Convert the following Moore machine into its 2 1 2

equivalent Mealy machine. 1

30 Convert the R.E. = (a|b)* into DFA 1 2 1 3

Construct CFG, G=({S,A,B}, {a,b},P,S) with
production set P as

S→ aAbB
31 3 2 3 3
A→ Ab|b
B → Ba|a

to CNF
32 Prove that L = {ww | w ∈ {0, 1} *} is not regular. 2 2 2 2
Part – III Module BL CO PO
Long Answer type Questions
Design a DFA over the alphabet {0,1} to accepts
1 1 3 1 3
all the string ends with 1.
Design a DFA over the alphabet {a,b} to accepts
2 1 3 1 3
a language L ={a, aa, aaa ,…}
Convert FA to Regular Expression.

3 2 3 2 2

Design a DFA over the alphabet {a,b} to accepts

4 1 3 1 3
all the string ends with b.
5 Design PDA which accepts all the strings 2 2 2 2
L={an.bn|n>=1} and find the ID for that
PDA.
6 Design the TM for the language L={an.b|n>=0} 4 1 4 1
7 Covert the following epsilon-nfa to nfa-

1 2 1 3

Convert the NFA with ε transition into its

equivalent DFA.

8 1 2 1 3

Minimize the dfa

9 1 3 1 3

Check whether the string “cbba” is a member of

the language L1 or not. The grammar for the
10 3 2 3 3
language is
S→ AB
 A→ a|c|CC
B→ b|BC
C→ CB|BA|c
Convert the following CFG to CNF
11 4 2 4 3
A→ A | A| p | q | z
Check whether the following language is CFL or
12 4 2 4 3
not L= {an.bn.cn | n>=1}
Define Ackermann Function, find out the
value of the following-
13 5 2 5 3
A(2,3)
A(1,3)
What is Post Correspondence Problem (PCP)?
Check whether any solution exist to the given
14 instance- 5 2 5 3
[a,aa],[bb,b],[a,bb]
[a,ab],[ba,aba],[bba,b]
Design a TM for finding the complement of any
15 4 3 4 3
binary number
Design a PDA for even length palindrome string
over the alphabet set {a,b,c} and trace the string
16 4 3 4 3
aaabcbaaa
aaabcaaab
17 Explain Church Turing Hypothesis in details. 4 3 4 3

Using CYK algorithm cheek whether the string

18 “baaba” is a valid member of the following CFG. 4 3 4 3
S→AB|BC
A→ BA|a
B→ CC|b
C→ AB|a

Draw a DFA for accepting all the strings the ends

19 1 2 1 3
with bbb over the alphabet set={a,b}
Design a NFA for the language L={a, ab, aab ,
20 aaab, …} and convert it into its corresponding 1 3 1 3
DFA