PANIMALAR ENGINEERING COLLEGE

(An Autonomous Institution, Affiliated to Anna University Chennai)

QUESTION BANK
Details of the Course
Name of the Department : COMPUTER SCIENCE AND BUSINESS SYSTEMS
Name of the Course : Formal Language and Automata Theory
Course Code : 23CB1302
Bloom’s Level: BL1 - Remembering, BL2 - Understanding, BL3 - Applying, BL4 - Analyzing, BL5 –
Evaluating, BL6 - Creating.

UNIT- I - INTRODUCTION AND FINITE AUTOMATA

Bloom’s Course Marks
PART A ( 2 Marks)
Level Outcome Allotted
1. Define deductive proof. Give example. [BL1] [CO1] [2]

2. State the differentiate NFA and DFA. [BL2] [CO2] [2]

3. What are productions and derivation in the context of formal [BL1] [CO1] [2]
grammars?
4. Construct FA to accept the string that always end with 00. [BL3] [CO2] [2]
5. Explain the Chomsky hierarchy of languages. [BL2] [CO1] [2]

Descriptive Questions ( 13 /15/16 Marks)

6. i) Prove by integer induction 1 2+ 22 + ... + n2 = n ( n + 1 )( 2n + 1 ) [BL5] [CO1] [13]
6
ii) Prove that theorem A language L is accepted by some DFA if
and only if L is accepted by some NFA.
7. Construct an NFA for the regular expression (a|b)*abb using [BL3] [CO2] [13]
Thompson’s construction.
8. Construct DFA equivalent to NFA ({p,q,r,s},{0,1}, δ,P, {S}),Where δ [BL3] [CO2] [13]
is
0 1
P {p,q} {p}
q {r} {r}
r {s} -
s s {s}
9. Construct the following DFA to a regular expression. [BL3] [CO2] [13]

10. Analyze the minimize DFA as given below. [BL6] [CO2] [15]

Couse Instructor Course Coordinator Head of the Department

Name & Designation Name & Designation
 UNIT- II - REGULAR LANGUAGES AND CONTEXT-FREE LANGUAGES
Bloom’s Course Marks
PART A ( 2 Marks)
Level Outcome Allotted
1. Show that one property of regular languages that does not hold for [BL2] [CO3] [2]
context-free languages.
2. List out the types of Normal Forms and give an example. [BL1] [CO3] [2]
3. State pumping lemma for regular languages. [BL1] [CO4] [2]

4. List out the four components of context free grammar (CFG). [BL1] [CO4] [2]
5. Construct a parse tree of (a+b)*c for the grammar [BL3] [CO4] [2]

Descriptive Questions ( 13 /15/16 Marks)

6. i)Construct a CFG for the language L= {WCWR/ W is a String in [BL3] [CO4] [13]
(a+b)* }
ii)Construct a CFG for the following language L=( 0 n1 n /n ≥ 1}
7. i)Explain the closure properties of regular Languages. [BL2] [CO3] [13]

ii) Prove the following statement with justification.

“The language L = {a i b j c i | i,j>0} is not regular”.
8. Construct the Chomsky normal form for the following grammar. [BL3] [CO3] [13]
S->AB | aB
A->aab | ℇ
B->bbA
9. Construct Left Most Derivation, Right Most Derivation and parse [BL3] [CO2] [15]
Tree
S→ a | ^ | (T)
T→T , S | S using input string ((( a , a) , ( ^ , a)) , a)
10. Build the grammar into GNF [BL6] [CO2] [13]
S→ AB
A→ BS | b
B→ SA | a

UNIT- III - PUSHDOWN AUTOMATA

Bloom’s Course Marks
PART A ( 2 Marks)
Level Outcome Allotted
1. Define Push Down Automata. [BL1] [CO3] [2]

2. Convert the following CFG to PDA. [BL2] [CO3] [2]

A→ 0A | 1A | 0 | 1
Couse Instructor Course Coordinator Head of the Department
Name & Designation Name & Designation
 3. Explain about instantaneous description of a PDA. [BL2] [CO3] [2]
4. How context-free language be recognized by a linear bounded [BL1] [CO3] [2]
automaton?
5. Explain the pumping lemma for context-sensitive languages. [BL2] [CO3] [2]

Descriptive Questions ( 13 /15/16 Marks)

6. Explain the Closure properties of Context Free Languages. [BL2] [CO3] [13]

7. Prove that L = { an bn cn | n ≥ 0 } is not a Context Free Language [BL5] [CO3] [13]

8. Design PDA for the language that accepts strings with na (w) < [BL6] [CO3] [13]
nb (w) where w ℇ (a + b)*
9. Explain about linear bounded automata (LBA) and discuss their [BL2] [CO3] [13]
equivalence with context-sensitive grammars (CSG). Provide an
example illustrating the capabilities of LBAs.
10. How PDA is converted into CFG? Convert the following PDA into [BL2] [CO3] [15]
CFG.
P = ({p,q},{0,1},{Z,X}, δ p, Z, ø)
δ (p,1, Z) ={(p,XZ)} δ (p,, Z) ={(p,)} δ (p,1,X )={(p,XX)}
δ (q,1,X) ={( q,)} δ (p,0,X) ={(q,X)} δ (q,0,Z ={(p,Z)}

UNIT- IV - TURING MACHINES

Bloom’s Course Marks
PART A ( 2 Marks)
Level Outcome Allotted
1. What is the basic model of a Turing machine (TM)? [BL1] [CO4] [2]

2. What is an unrestricted grammar? [BL1] [CO4] [2]

3. Define nondeterministic Turing Machine(NTM) and draw [BL2] [CO5] [2]

transition diagram for an NTM that accepts the language {1n | n
> 4}
4. What role do Turing machines play as enumerators ? [BL1] [CO5] [2]

5. Design a TM for finding 1’s complement of a given binary [BL3] [CO5] [2]
number.
Descriptive Questions ( 13 /15/16 Marks)
6. Construct a TM for the subroutine f (a, b) = a * b where a and b [BL3] [CO5] [13]
are unary numbers
7. Construct TM to accept palindrome in an alphabet set ∑={a,b} [BL3] [CO5] [13]
Trace the strings“abab”and “baab”
8. Design Turing Machine M for f(x,y)=x*y where x,y are stored in [BL4] [CO5] [13]
the tape intheform0x10y1
9. Prove that the following languages are recursive or recursively [BL5] [CO4] [13]
enumerable
a) Union of two recursive languages
b) Intersection of two recursively enumerable languages
c) The language L and its complement L are recursively
enumerable languages, and then L is recursive.
10. Construct a TM for a language having equal number of a’s and [BL3] [CO5] [15}
b’s in it over the input set ∑ ={a , b}

Couse Instructor Course Coordinator Head of the Department

Name & Designation Name & Designation
 UNIT- V - UNDECIDABILITY AND COMPLEXITY
Bloom’s Course Marks
PART A ( 2 Marks)
Level Outcome Allotted
1. What is the Church-Turing thesis? [BL1] [CO6] [2]

2. State Cook's theorem in the theory of NP-completeness. [BL1] [CO6] [2]

3. State two languages , which are not recursively enumerable. [BL1] [CO3] [2]
4. Provide an example of an undecidable problem about [BL2] [CO6] [2]
languages.
5. What is Universal Turing Machine ? [BL1] [CO5] [2]

Descriptive Questions ( 13 /15/16 Marks)

6. Explain the concept of a universal Turing machine. Describe how [BL2] [CO5] [13]
it operates and its significance in the theory of computation.
7. Discuss the concept of diagonalization languages and their role [BL6] [CO6] [13]
in demonstrating undecidability. Provide an example of a
diagonalization language and explain why it is undecidable.
8. State and explain Rice’s theorem [BL1] [CO6] [13]
9. Explain the classes and definition of P and NP problems [BL5] [CO6] [13]
10. Discuss the difference between NP complete and NP hard [BL6] [CO6] [13]
problems

Couse Instructor Course Coordinator Head of the Department

Name & Designation Name & Designation