Toc QB

Download as pdf or txt
Download as pdf or txt
You are on page 1of 34

INSTITUTE OF AERONAUTICAL ENGINEERING

(Autonomous)
Dundigal, Hyderabad - 500 043

INFORMATION TECHNOLOGY
QUESTION BANK

Department INFORMATION TECHNOLOGY


Course Title THEORY OF COMPUTATION
Course Code AITC04
Program B.Tech
Semester IV
Course Type Core
Regulation UG-20
Theory Practical
Course Structure Lecture Tutorials Credits Laboratory Credits
3 1 4 - -
Course Coordinator Dr.U Sivaji, Associate Professor

COURSE OBJECTIVES:
The students will try to learn:

I The fundamental knowledge of automata theory which is used to solve


computational problems.
II TThe reorganization of context free language for processing infinite information
using push down automata..
III The computer based algorithms with the help of an abstract machine to solve
recursively Enumerable problems.

COURSE OUTCOMES:
After successful completion of the course, students should be able to:
CO 1 Make use of deterministic finite automata and non deterministic Apply
finite automata for modeling lexical analysis and text editors.
CO 2 Extend regular expressions and regular grammars for parsing and Understand
designing programming languages.
CO 3 Illusrate the pumping lemma on regular and context free Understand
languages for perform negative test .
CO 4 Demonstarte context free grammars, normal forms for generating Understand
patterns of strings and minimize the ambiguity in parsing the given
strings.
CO 5 Construct push down automata for context free languages for Apply
developing parsing phase of a compiler.
CO 6 Apply Turing machines and Linear bounded automata for Apply
recognizing the languages,complex problems.

QUESTION BANK:
Q.No QUESTION Taxonomy How does this subsume CO’s
the level
MODULE I
FINITE AUTOMATA
PART A-PROBLEM SOLVING AND CRITICAL THINKING QUESTIONS
1 Describe NFA for accepting Understand This would require the CO 1
any binary string that learner to recall the Non
contains 11 as a substring Deterministic finite
and Convert to DFA. automata and discuss the
steps for the construction of
NFA and the conversion of
NFA to DFA.
2 Convert NFA with ϵ to Understand This would require the CO 1
equivalent DFA learner to recall the finite
automata and show the
steps for the conversion of
NFA with ϵ to DFA.

3 Describe a DFA that any Understand This would require the CO 1


given decimal number is learner to recall the
divisible by 5 Deterministic finite
automata and discuss the
steps for the construction of
DFA.
4 Describe a DFA for the Understand This would require the CO 1
followinglanguage learner to recall the
L={w/ |w| mod 5=0,w Deterministic finite
belongs to (a,b)*} automata and discuss the
L={w/ |w| mod 5=1,w steps for the construction of
belongs to (a,b)*} DFA.

Page 2
5 Convert NFA with ϵ to Understand This would require the CO 1
equivalent NFA learner to recall the finite
M=({q0,q1,q2},{0,1,2}, δ, automata,and show the
q0, {q2}) where δ is given steps for the conversion of
by NFA with ϵ to NFA.
[δ (q0,0)={q0}, δ (q0,1)=ϕ,
δ (q0,2)=ϕ, δ(q0, ϵ)=q1]
[δ (q1,0)=ϕ, δ (q1,1)=q1 , δ
(q1,2)=ϕ ,δ (q1, ϵ)=q2]
[δ (q2,0)=ϕ, δ (q2,1)= ϕ , δ
(q2,2)= {q2},δ (q2, ϵ)= ϕ] .
6 Demonstrate NFA that Understand This would require the CO 1
strings such that the third learner to recall the Non
symbol from the rightPend is Deterministic finite
a 0 over an alphabet automata and discuss the
={0,1}. And Convert it into steps for the construction of
equivalent DFA. NFA and the conversion of
NFA to DFA.
7 Convert the NFA to Understand This would require the CO 1
equivalent DFA, as shown in learner to recall the finite
fig. below automata and show the
steps for the conversion of
NFA to DFA.

.
8 Describe the transition Understand This would require the CO 1
Table for the below NFA learner to recall the finite
and then convert its automata and show the
equivalent transition steps for the conversion of
diagram for DFA. NFA to DFA.

Page 3
9 Describe a DFA that will Understand This would require the CO 1
accept
P those words from learner to recall the
= {a, b} where the Deterministic finite
number of a’s is divisible by automata and discuss the
two and the number of b’s is steps for the construction of
divisible by three. Sketch DFA.
the transition table of the
finite automata.
10 Describe a DFA that will Understand This would require the CO 1
accept thoseP words from learner to recall the finite
alphabets = {a, b} where automatand discuss the
the number of bs is divisible steps for the construction of
by three. Sketch the DFA.
transition table and diagram
of the finite Automata.
11 Design a Moore machine for Understand This would require the CO 1
a binary input sequence learner to recall the finite
such that if it has a automat and discuss the
substring 101, the machine steps for the construction of
output A, if the input has Moore machine.
substring 110, it outputs B
otherwise it outputs C.
12 Design a Mealy machine for Understand This would require the CO 1
a binary input sequence learner to recall the finite
such that if it has a automata and discuss the
substring 101, the machine steps for the construction of
output A, if the input has mealy machine.
substring 110, it outputs B
otherwise it outputs C.
PART-B LONG ANSWER QUESTIONS
1 Explain the concept of Understand This would require the CO 1
alphabet, string and learner to recall the finite
language with suitable automata and discusswith
examples each. the basic example.
2 Give a brief note on Understand This would require the CO 1
deterministic finite learner to recall the finite
automaton and automata and discuss the
non-deterministic finite steps for the construction of
automaton with example DFA and NFA
each.
3 List out the various Remember - CO 1
differences between DFA
and NFA

Page 4
4 Describe how various rules Understand -This would require the CO 1
used for construction of ϵ learner to recall the finite
NFA with suitable example automata and show the
and also write th steps for steps for the conversion of
NFA with ϵ to NFA NFA with ϵ to NFA.
conversion with an example.
5 Describe a a procedure for Understand This would require the CO 1
converting NFA to DFA learner to recall the
with suitable example and Deterministic finite
also discuss about discuss automata and discuss the
about Finite Automata with steps for the construction of
Epsilon- Transitions DFA.
6 Define Regular Expression? Remember - CO 1
what are the rules of
Regular Expression and
what operations performed
on Regular Expression each
with an example.
7 Construct a DFA for the Understand This would require the CO 1
Regular expression (0+1)* learner to recall the
(00+11) (0+1)*. Deterministic finite
automata and discuss the
steps for the construction of
DFA
8 Design deterministic finite Understand This would require the CO 1
automata (DFA) for the learner to recall the
following
P languages shown Deterministic finite
below = { a,b} automata and discuss the
a) L={w | w is any string steps for the construction of
that max 3 a’s and any DFA
number of b’s}
b) L={w | w is any string
that contain atmost three
a’s}
9 Convert the following NFA Understand This would require the CO 1
with ϵ to NFA. learner to recall the finite
automata and show the
steps for the conversion of
NFA with ϵ to NFA

Page 5
10 Describe Finite Automata Understand This would require the CO 1
and draw FA for the
P strings learner to recall the finite
over an alphabet ={ automata and discuss the
0,1} steps for the construction of
a. The string with even FA
number of 0’s and even
number of 1’s
b. The string with odd
number of 0’s and odd
number of 1’s
11 Describe a DFA, the Understand This would require the CO 1
language recognized by the learner to recall the
Automaton being L={w | w Deterministic finite
contains either the automata and discuss the
substrings ab or ba}.Draw steps for the construction of
the transition table. FA
12 Convert the following NFA Understand This would require the CO 1
into DFA learner to recall the finite
automata and show the
steps for the conversion of
NFA to DFA.

13 Design a DFA for the Understand This would require the CO 1


following language learner to recall the
L={|w| mod3=0,w belongs Deterministic finite
to (a,b)*} automata and discuss the
L={| w | mod3=1,w belongs steps for the construction of
to (a,b)*} DFA

14 Describe a DFA for the Understand This would require the CO 1


following P
language over an learner to recallthe
alphabet = { 0,1} Deterministic finite
a)The string with odd automata and discuss the
number of 0’s and even steps for the construction of
number of 1’s DFA
b)The string with even
number of 0’s and odd
number of 1’s

Page 6
15 Convert the following NFA Understand This would require the CO 1
into equivalent DFA. learner to recallthe
Deterministic finite
automata and show the
steps for the conversion of
NFA to DFA.

16 Convert the following NFA Understand This would require the CO 1


with ϵ to NFA withot ϵ learner to recallthe finite
automata and show the
steps for the conversion of
NFA-ϵ to DFA.

17 Design ϵ -NFA for Regular Understand This would require the CO 1


Language L = (0+1)*(00 + learner to recall the
11) and L = ab + ba Deterministic finite
automata and discuss the
steps for the construction of
DFA
18 Convert the following NFA Understand This would require the CO 1
with ϵ to NFA. learner to recallthe finite
automata and show the
steps for the conversion of
NFA-ϵ to DFA.

19 Draw transition diagram Understand This would require the CO 1


and also transition table for learner to recall the
language that accepts all Deterministic finite
strings of length at least 2. automata and discuss the
steps for the construction of
DFA

Page 7
20 Design a mealy machine Understand This would require the CO 1
that scans sequence of input learner to recall the finite
of 0 and 1 and generates automata and discuss the
output ’A’ if the input steps for the Mealy machine
string terminates in 00,
output ’B’ if the string
terminates in 11, and
output ’C’ otherwise.
21 Design a Moore machine Understand This would require the CO 1
with the input alphabet {0, learner to recall the finite
1} and output alphabet {Y, automata and discuss the
N} which produces Y as steps for generation of
output if input sequence moore machine
contains 1010 as a substring
otherwise, it produces N as
output..
22 Compare between Mealy UnderstandThis would require the CO 1
Machine and Moore learner to recall the finite
Machine with examples. automata and discuss the
Difference between Mealy
Machine moore machine
PART-C SHORT ANSWER QUESTIONS
1 Define DFA. Remember - CO 1
2 Differentiate between DFA Understand This would require the CO 1
and NFA. learner to textbfrecall the
finite automata and
textbfexplain the differences
between NFA and DFA
3 Define the String with an Remember - CO 1
example.
4 Define transition function of Remember - CO 1
DFA.
5 Define NFA with Remember - CO 1
ϵ–transitions.
6 Define power of an alphabet Remember - CO 1
( ⋆ ).
P

7 List the applications of Remember - CO 1


finite automata.
8 Define Null string. Remember - CO 1
9 Define Kleene Star? Remember - CO 1
10 Define NFA with example. Remember - CO 1
11 Describe transition diagram Remember - CO 1
for DFA accepting string
ending with 00

Page 8
12 Describe DFA for a string Remember - CO 1
accepting odd number of 1’s
and even number of 0’s.
13 Describe transition diagram Remember - CO 1
for DFA to accept exactly
one ‘a’ defined
P over an
alphabet = {a,b}.
14 Demonstrate DFA for odd Understand This would require the CO 1
number of 1’s. learner to recall the
Deterministic finite
automata and discuss the
steps for the construction of
DFA
15 Define ϵ - closure. Remember - CO 1
16 Describe FSM and its Remember - CO 1
structure with an example.
17 State the Mathematical Remember - CO 1
definition of Finite
Automata.
18 Demonstrate DFA for even Understand This would require the CO 1
number of 1’s. learner to recall the
Deterministic finite
automata and discuss the
steps for the construction of
DFA
19 State the reasons of NFA’s Remember - CO 1
with epsilon moves more
powerful than NFA’s
without epsilon moves
20 Demonstrate DFA for the Understand his would require the learner CO 1
language accepting strings to recall the Deterministic
which contains 001 as finite automata and discuss
substring. the steps for the
construction of DFA
21 Define Mealy Machine with Remember - CO 1
example.
22 Define Moore Machine with Remember - CO 1
example.
MODULE II
REGULAR LANGUAGES
PART-A PROBLEM SOLVING AND CRITICAL THINKING QUESTIONS

Page 9
1 Convert Regular Expression Understand This would require the CO 2
[ ab + (b + aa)b* a ] to learner to recall the
Finite Automata.Draw the Regular Expression and
Transition Table For NFA show the steps for the
conversion of Regular
Expression to Finite
Automata.
2 convert the given finite Understand This would require the CO 2
automata to regular learner to recall the
expression. Regular Expression and
show the steps for the
conversion of Regular
Expression to Finite
Automata.

3 Describe Pumping Lemma Understand This would require the CO 2


for Regular Languages. learner to recall the
Prove that the language Regular Languages and
L = {ai bi | i >= 0} is not show the steps for for the
regular checking the language is not
regular.
4 Describe the DFA Understand This would require the CO 1
Transition diagram for learner to recall the
equivalent Regular Regular Expression and
expression (bb)*(aa)* show the steps for for the
conversion of Regular
Expression to Deterministic
Finite Automata
5 Convert the following Understand This would require the CO 2
Regular Expression (0 + learner to recall the
1)*(00 + 11) to epsilon Regular Expression and
NFA. show the steps for for the
conversion of Regular
Expression to Deterministic
Finite Automata
6 Convert the following Understand This would require the CO 1
Regular expression learner to recall the
(0+1)*(01+110)10 + (0 + Regular Expression and
11)0* 1 to DFA. show the steps for for the
conversion of Regular
Expression to Non
Deterministic Finite
Automata

Page 10
7 Convert the following Understand This would require the CO 2
automata into Regular learner to recall the Finite
expression Automata and show the
M=({q1,q2,q3},{0,1}, δ, q1, steps for the conversion of
{q2,q3}) where δ is given by Finite Automata to Regular
[δ (q1,0)={q2}, δ Expression.
(q1,1)={q3}]
[δ (q2,0)={q1}, δ
(q2,1)={q3}]
[δ (q3,0)={q2}, δ (q3,1)=
{q2}]

8 Describe the following Understand This would require the CO 2


language is not regular learner to recall the
i)L = { an bn | n is a positive
P Regular Languages and
integer } over alphabet show the steps for the
= { a,b} checking the language is not
ii) L= {an b2n | n≥0 } regular.

9 Convert the automata in Understand This would require the CO 2


which strings endPwith 101 learner to recall the Finite
over an alphabet ={0,1} Automata and show the
to the Left Linear Grammar steps for the conversion of
and Right Linear grammar. Finite Automata to Regular
Grammars.
10 Convert the following Finite Understand This would require the CO 1
Automata to regular learner to recall the Finite
expression. Automata and show the
steps for the conversion of
Finite Automata to Regular
Expression.

PART-B LONG ANSWER QUESTIONS


1 Convert Regular Expression Understand This would require the CO 1
01* + 1 to Finite Automata. learner to recall the
Regular Expression and
show the steps for the
conversion of Regular
Expression to Finite
Automata.

Page 11
2 Convert Regular Expression Understand This would require the CO 2
01* + 1 Right linear, Left learner to recall the Regular
linear Regular Grammars Expression and show the
steps for the conversion of
Regular Expression to
Regular Grammars.
3 Describe Regular Remember - CO 2
expression? Simplify the
following Regular
Expression
i)ϵ+1*(011)*(1*(011)*)*=
(1+011)*
ii)(0 + 11 ∗ 0) + (0 + 11 ∗
0)(10+10∗1)∗(10+10∗1)∗ =
1 ∗ 0(10 + 10 ∗ 1)∗
4 Convert the given Finite Understand This would require the CO 1
Automata (a+b)*ab* to learner to recall the Finite
Regular grammar . Automata and show the
steps for the conversion of
Finite Automata to Regular
Grammar.
5 Convert the given Finite Understand This would require the CO 1
Automata 0*11(0+1)*to learner to recall the Finite
Regular grammar . Automata and show the
steps for the conversion of
Finite Automata to Regular
Grammar.
6 Describe Regular Remember - CO 2
expression, Regular set and
Finite Automata.
Distinguish those with
example representations.
7 Convert Regular Expression Understand This would require the CO 2
(0+1)*00(0+1)* to the learner to recall the Regular
Finite Automata(NFA-ϵ) . Expression and show the
steps for the conversion of
Regular Expression to
Finite Automata.
8 Convert Regular Expression Understand This would require the CO 2
(b+aa)*a* to Finite learner to recall the Regular
Automata(NFA-ϵ). Expression and show the
steps for the conversion of
Regular Expression to
Finite Automata.

Page 12
9 State Pumping Lemma for Remember - CO 2
Regular Languages with a
suitable example and also
write about the identity
rules of Regular
Expressions.
10 Convert given Regular Understand This would require the CO 2
expression (a* + b* ) to learner to recall the Regular
NFA-ϵ. Expression and show the
steps for the conversion of
Regular Expression to
Finite Automata.
11 Convert the following Understand This would require the CO 2
automata into Regular learner to recall the Finite
expression Automata and show the
M=({q1,q2,q3},{0,1}, δ, q1, steps for the conversion of
{q1}) where δ is given by Finite Automata to Regular
[δ (q1,0)={q1}, δ expression
(q1,1)={q2}]
[δ (q2,0)={q3}, δ
(q2,1)={q2}]
[δ (q3,0)={q1}, δ (q3,1)=
{q2}]
12 Describe Pumping lemma. Remember - CO 2
Prove that the language
L={wwr y | w,y
belongs{0, 1}+ }is not
regular.
13 Describe Regular grammar? Remember - CO 2
Explain the types of regular
grammar with examples.
14 IIustrate the steps for Understand This would require the CO 2
conversion of regular learner to recall the Regular
grammar to finite Grammar and show the
automata? Construct the steps for the conversion of
FA for the following Regular Grammar to Finite

grammar S aS/bA/b Automata.

,A aA/bS/a
15 Convert the given Regular Remember - CO 2
Expression 10 + (0 + 11)0*
1 to FA and convert it into
NFA.

Page 13
16 Show that the following Remember - CO 2
languages is not regular L =
{an bn | n≥ 1}
L={aP | p is prime}
17 Convert the following Understand This would require the CO 2
regular expression to learner to recall the Regular
Regular grammar Expression and show the
(0+1)*00(0+1)* steps for the conversion of
Regular Expression to
Regular Grammar.
18 Describe the Left Linear Remember - CO 2
Grammar for the strings
start withP ‘a’ over an
alphabet ={a,b}.
19 Illustrate the steps for Understand This would require the CO 1
conversion from Finite learner to recall the Finite
Automata to Regular Automata and show the
Expression with example? steps for the conversion of
Finite Automata to Regular
Expression.
20 Describe Pumping lemma. Remember - CO 3
Prove that the language is
reular L = {xwwr y| w,x,y
belongs to {a,b}+ }
PART-C SHORT ANSWER QUESTIONS
1 Define Regular Languages. Remember - CO 2
2 List out any two Remember - CO 2
applications of regular
expression.
3 Define Pumping Lemma for Remember - CO 3
Regular Languages.
4 Show an example for a - CO 2
regular set?
5 Define the Regular Remember - CO 2
Expression for the empty
string.
6 Describe regular expression Understand This would require the CO 2
for denoting language learner to recall regular
containing empty. languages and explain the
regular expressions for given
laguage.
7 Define right linear Remember - CO 4
grammars.

Page 14
8 Show the Regular Remember - CO 2
Expression for the set of
binary strings.
9 Define Regular grammars. Remember - CO 3
10 List out the advantages of Remember - CO 2
regular expressions.
11 Define Regular set? Remember - CO 2
12 Describe regular expressions Understand This would require the CO 2
for the Set of strings over 0, learner to recall strings,
1 whose last two symbols regular expressions and
are the same. explain the regular
expressions for given set of
strings.
13 Describe the regular Understand This would require the CO 2
language generated by learner to recall regular
regular expression expressions and explain the
(0+1)*001(0+1)*. languages for given
expression.
14 List the difference between Remember - CO 4
left linear and right linear
grammars.
15 Describe the Regular Understand This would require the CO 3
Expression to generate
P at learner to recall regular sets
least one b over ={a,b} and explain the regular
expression for given regular
set.
16 Describe that following Remember - CO 2
languages are not regular
L={an bm | n, m and n<m }
17 Describe that following Remember - CO 2
languages are not regular
L={an | n is a perfect square
}
18 Define Regular Expression Remember - CO 2
for even number of 0’s.
19 Define Regular Expression Remember - CO 2
for odd number of 0’s.
20 Define Regular Expression Remember - CO 2
for the regular sets consists
strings having two
consecutive a’s.
MODULE III
CONTEXT FREE GRAMMARS

Page 15
PART A-PROBLEM SOLVING AND CRITICAL THINKING QUESTIONS
1 Describe a grammar for Understand This would require the CO 3
valid expressions over learner to recall the context
operator - and /. The free grammars and explain
arguments of expressions the left most derivation and
are valid identifiers over Right most derivation
symbols a,b, 0 and Derive
Left Most Derivation and
Right Most Derivation for
string W= (a11-b0) /
(b00-a01). Draw parse tree
for Left Most Derivation.

2 Describe Leftmost Understand This would require the CO 3


Derivation. , Rightmost learner to recall the context
Derivation,Derivation Tree free grammars and explain
for the following grammar the left most derivation and
with respect to the string Right most derivation.

aaabbabbba. S aB | bA ,
 
A aS | bBA | a , B bS |
aAB | b
3 Convert the following Understand This would require the CO 4
grammar into GNF learner to recall the context

S ABA/AB/BA/AA/B free grammars and explain
 
A aA/a, B bB/b the steps for the conversion
of the CFG to GNF.
4 Describe the context free Understand This would require the CO 4
grammars in the four tuple learner to recall the context
form.(V,T,P,S) Pfor the given free grammars and explain
languages on ={a,b} the CFG for the given set of
i. All strings having at least strings.
two a’s
ii. All possible strings not
containing triple b’s
5 Describe the string Understand This would require the CO 4
“aabbabba” for leftmost learner to recall context
derivation and rightmost free grammars and explain
derivation using a CFG the rleft most derivation
given by and Right most derivation

S Ab|Ba

A a| aS| Baa

B b | bS |aBB

Page 16
6 Describe the minimized Understand This would require the CO 4
CFG productions for CFG learner to recall context
 
S Ab|Bb , A a |aS |Baa free grammars and explain

B b|bS |aBB the steps for the
minimization of the CFG.
7 Convert the following Understand This would require the CO 4
grammar into GNF learner to recall context
 
A1 A2A3 ,A2 A3A1 | b, free grammars and explain

A3 A1 A2 | a the steps for the conversion
of the CFG to GNF
8 Convert the following Understand This would require the CO 4
grammar into Chomsky learner to recall context
Normal form L(G) – free grammars and explain

S AaA | CA | the steps for the conversion

BaB,A aaBa | CDA | aa | of the CFG to CNF.

DC ,B bB | bAB | bb |

aS, C Ca | bC | D, D
 bD | A
9 Describe the steps to show UnderstandThis would require the CO 4
the following is not CFG. learner to recall context
L= { an bn cn | n≥ 0 } free grammars and explain
the steps for the checking of
the given grammar is CFG
or not.
10 Describe the CFG for the Understand This would require the CO 4
language L={an b2n where learner to recall context
n≥1}and Explain the steps free grammars and explain
for the minimization of the the for the minimization of
CFG the CFG“
PART-B LONG ANSWER QUESTIONS
1 Describe Leftmost Remember - CO 4
Derivation. , Rightmost
Derivation, Derivation Tree
for the following grammar
with respect to the string

aaabbabbba. S aB |
 
bA,A aS| bAA|a B bS |
aBB | b
2 Describe a CFG for the Remember - CO 4
languages L={ai bj | i≤2j}

Page 17
3 Describe leftmost and Remember - CO 4
rightmost derivations for
the strings, if the language

is given as S AS | ϵ,

A aa|ab|ba|bb
Strings:
aabbba
baabab
aaabbb
4 Explain about the Understand This would require the CO 4
enumeration of properties of learner to recall the
context free language context free grammars and
Explain the steps for the
minimization of the CFG.
5 write the procedure for Understand This would require the CO 4
finding Ambiguity in learner to recall the context
context free grammars and free grammars and Explain
also minimization of CFG the steps for the
with example. minimization of the CFG
6 Discuss about: a) Context Understand This would require the CO 4
Free Grammar b) Left Most learner to recall the
Derivation c) Right Most context free grammars and
Derivation. Explain the steps for the
minimization of the CFG
7 Convert the grammar to Understand This would require the CO 4
CNF learner to recall the
 
S aSa/aa,S bSb/bb context free grammars and

S a/b. Explain the steps for the
minimization of the CFG
8 Describe Chomsky Normal Remember - CO 4
Form and Greibach Normal
Form each with an example.
9 Define Normalization of Remember - CO 4
CFG? What is the use of
Normalization? Explain
different types of normal
forms.
10 Illustrate the construction Understand This would require the CO 4
of Greibach normal form learner to recall the context
with an example. free grammars and Explain
the steps for the conversion
of the CFG into GNF

Page 18
11 Show that the following Understand - CO 4
CFG ambiguous. S iCtS | 

iCtSeS | a, C b.
12 Describe the Pumping Remember - CO 4
lemma for Context Free
Languages concept with
example{an bn cn where n≥0}.
13 Describe the minimized Remember This would require the CO 4
CFG productions in S  learner to recall the context
aS1b, S1  a S1b/ ϵ free grammars and Explain
the steps for the
minimization of the CFG.
14 Convert the following CFG Understand This would require the CO 4

into GNF. S AA/a,A  learner to recall the context
SS/b free grammars and Explain
the steps for the conversion
of the CFG to GNF.
15 Describe unit production? Remember - CO 4
Explain the procedure to
eliminate unit production.
16 Describe the procedure to Remember - CO 4
eliminate ϵ productions in
grammar.
17 Convert the following Understand This would require the CO 4
grammar into GNF learner to recall the context
G=({A1,A2,A3},{a,b},P,A) free grammars and Explain

A1 A2A3, A2 A3A1/b the steps for the conversion

,A3 A1A2/a of the CFG to GNF.
18 Describe the minimized Understand This would require the CO 4
CFG productions from the learner to recall the context
following grammar free grammars and Explain

A aBb/bBa ,B aB/bB/ϵ the steps for the
minimization of the CFG
19 Describe CFG and Explain Understand This would require the CO 4
a CFG for the following learner to recall the context
language L = { 0i 1j 0k | j > i free grammars and Explain
+ k }and write the the steps for the
minimization steps. minimization of the CFG.
20 Describe the minimized Understand This would require the CO 4
CFG for the following learner to recall the context

grammar S ABCa | bD, free grammars and Explain
 
A BC | b, B b | ϵ C | ϵ,  the steps for the

D d minimization of the CFG.

Page 19
21 Covert the CFG to Understand This would require the CO 4
Greiback Normal form by learner to recall the context
taking an example free grammars and Explain
the steps for the conversion
of the CFG to GNF.
22 Convert the grammar G Understand This would require the CO 4
 
given by S aAa, A Sb| learner to recall the context

bcc|DaA, C abb| DD, E  free grammars and Explain

ac, D aDa the steps for the
into an equivalent grammar minimization of the CFG.
by removing useless symbols
and useless productions
from it.
PART-C SHORT ANSWER QUESTIONS
1 Define a context free Remember - CO 4
grammar( CFG).
2 Define the parse tree with Remember - CO 2
example.
3 Differentiate the Rightmost Understand This would require the CO 4
derivation with Left most learner to recall the context
derivation with example. free grammars and Explain
the differences between
right most derivation and
left most derivation.
4 Describe a short notes Remember - CO 4
about leftmost derivation
with example.
5 CList any two applications Remember - CO 4
of Context Free Grammar.
6 Define the left sentential Remember - CO 4
form?
7 Describe the different ways Remember - CO 4
to derive a string from a
CFG.
8 Describe the language Remember - CO 4
generated by CFG or G?
9 Describe the concept of URemember - CO 2
parse tree?
10 Describe the concept of Remember - CO 2
subtree.
11 DDescribe the CFL for Remember - CO 4
 
S aSb | aAb , A bAa ,

A ba.

Page 20
12 Describe the usage of Remember - CO 4
normalization?
13 Define the ambiguous Remember - CO 3
grammar with example?
14 Describe the language Remember - CO 3
generated by the following
grammar

S AB

A aAa|bAb|a|b

B Ab|Bb| ϵ
15 List the steps for the CFG Remember - CO 3
to reduce UNIT production.
16 Describe the elimination of Remember - CO 3
useless symbols in
productions.
17 List the steps for the given Remember - CO 3
grammar to get the
minimized CFG
S  
a S/A, A a / B

18 Describe the ambiguity Remember - CO 3


concept in CFG with an
example
19 Differentiate the CNF and Understand This would require the CO 3
GNF. learner to recall the
normalization of context
free grammars and Explain
the differences between
CNF and GNF.
20 List the steps for the given Remember - CO 3
grammar to get the
minimized CFG - S ? aS1b
S1?aS1b/?.
MODULE IV
PUSH DOWNAUTMATA
PART A- PROBLEM SOLVING AND CRITICAL THINKING QUESTIONS
1 Construct PDA for equal Apply This would require the CO 5
number of x’s and y’s. eg: learner to recall the
xyyxxy Context Free Grammars
and Explain the concept of
the PDA and Apply the
concepts for the construct of
the PDA

Page 21
2 Construct NDPDA for L = Apply This would require the CO 5
{ WWR | W ∈( X + Y)∗ } learner to recall the
Context Free Grammars
and Explain the concept of
the PDA and Apply the
concepts for the construct of
the NPDA
3 Convert the following PDA Understand This would require the CO 5
to CFG δ(q0,0,z0)=q0,xz0) learner to recall the Push
d(q0,0,x)=(q0,xx) Down Automata and
δ(q0,1,x)=(q1,ϵ) δ(q1,1,x) = Explain the steps for the
(q1,ϵ) δ(q1,ϵ,x)=(q1,ϵ) conversion of PDA CFG
δ(q1,ϵ,z0)=(q1,ϵ)
4 Construct DPDA for L = { Apply This would require the CO 5
W = WR | W ∈ ( X + Y)∗ } learner to recall the
Context Free Grammars
and Explain the concept of
the PDA and Apply the
concepts for the construct of
the DPDA
5 Design the pushdown Apply This would require the CO 5
automata for language learner to recall the
{an bn | n > 0} using final Context Free Grammars
state. and Explain the concept of
the PDA and Apply the
concepts for the construct of
the PDA
6 Construct a PDA with final Apply This would require the CO 5
state acceptance for the learner to recall the
language B= { Context Free Grammars
$
bin(i) mir(bin(i+1)) | i ≥0 and Explain the concept of
} ⊆ {0, 1, $}∗ the PDA and Apply the
Here is bin(i)∈{0,1}∗ the concepts for the construct of
binary the PDA
representation (without
leading zero’s) of the
number i.
Eg. bin(11) =1011 and
mir(bin(12)) =0011

Page 22
7 Construct CFG Apply This would require the CO 5
corresponding to PDA learner to recall the
whose transition mapping is Context Free Grammars
as follows. and Explain the concept of
δ(S,a,X)= (s, A,X) the PDA and Apply the
δ(S,b,A) =(s, AA) concepts for the conversion
δ(S,a,A) = (s, AA) of the PDA to CFG.
8 Show that given CFG with Apply This would require the CO 5
following productions learner to recall the

S aBc Context Free Grammars
 
A abc,B aAb,C AB, and Understand the concept

C c constructs a PDA M of the PDA and Apply the
such that the language concepts for the construct of
generated by M and G are the PDA.
equivalent.
9 Construct a PDA for the Apply This would require the CO 5
following grammar. learner to recall the

S 0A Context Free Grammars

A 0AB ,B 1  and Explain the concept of
the PDA and Apply the
concepts for the construct of
the PDA
10 Construct PDA for the Apply This would require the CO 5
following grammar learner to recall the

S AA | a Context Free Grammars

A SA | b and Explain the concept of
the PDA and Apply the
concepts for the construct of
the PDA.
PART-B LONG ANSWER QUESTIONS
1 Define the Remember - CO 5
NPDA(Nondeterministic
PDA) and
DPDA(deterministic PDA)
equivalent? Illustrate with
an example.

Page 23
2 Describe the grammar for Understand This would require the CO 5
the following PDA. learner to recall the Push
M=({q0, Down Automata and
q1},{0,1},{X,z0},δ,q0,Z0,ϕ) Explain the steps for the
and where δ is given by construct of the CFG from
δ(q0,0,z0)={(q0,XZ0)}, PDA
δ(q0,0,X)={(q0,XX)},
δ(q0,1,X)={(q1, e)},
δ(q1,1,X)={(q1, e)},
δ(q1, e,X)={(q1, e)},
δ(q1, e, Z0 )={(q1, e)}.
3 Describe PDA for string of Understand This would require the CO 5
form an b2n n≥1 learner to recall the Push
Down Automata and
Explain the steps for the
construct of the PDA.
4 Define PDA mathematically. - CO 5
With a neat diagram
explain the working of a
acceptance by final state
and acceptance by empty
stack and its equivalence
5 Describe the equivalence of Understand This would require the CO 5
context free language and learner to recall the Push
pushdown automata Down Automata and
Explain the CFG accepts
the given language.
6 Describe a PDA for the Understand This would require the CO 5

following grammar S 0A, learner to recall the Push

A 0AB/1,B 1  Down Automata and
Explain the steps for the
construct of the PDA
7 Prove that L is accepted by Understand This would require the CO 5
a PDA M1 by empty store, learner to recall the Push
if and only if L is accepted Down Automata and
by a PDA M2 by final state Explain the steps for the
conversion of PDA to CFG
8 Describe the PDA Understand This would require the CO 5
mathematically. Describe learner to recall the Push
the PDA for the following Down Automata and
language. L= {w | w of Explain the steps for the
form an bn }. construct of the PDA

Page 24
9 Describe PDA For the Understand This would require the CO 5
language L = {xcxr | x∈ learner to recall the Push
{a,b}∗ }and trace it for Down Automata and
string ’bacab’ Explain the steps for the
construct of the PDA
10 Describe the Pushdown Understand This would require the CO 5
automaton A is specified by learner to recall the Push
M=({q0,q1},{a,b},{X,Z}, Down Automata and
δ,qin , Z,ϕ) and where δ Explain the steps for the
contains the following construct of the PDA
transitions:
δ(q0,a,Z)=(q0,λ)
δ(q0,a,Z)=(q0,Xzin )
δ(q0,a,X)=(qo,XX)
δ(q0,b,X)=(q1,λ)
δ(q1,b,X)=(q1,λ)
δ(q1,a,z0)=(qo,Z)
Infer a (reduced)
context-free grammar G for
the empty stack language of
A, i.e., L(G) = Le(A).
11 Describe PDA for the below Understand This would require the CO 5
grammar as shown below learner to recall the Push

S aABB |aAA Down Automata and

A aBB |a Explain the steps for the

B BB | A construct of the PDA
that accepts the language
generated by given grammar
12 Describe a PDA for the Understand This would require the CO 5
below CFG which generates learner to recall the Push
the palindrome accepted by Down Automata and

L(G) S aSa| bSb|a|b Explain the steps for the
construct of the PDA
13 Define a PDA and describe Understand This would require the CO 5
a context free grammar for learner to recall the Push
the language Down Automata and
L={ai bj ck ; i < jorj < k} Explain the steps for the
construct of the PDA

Page 25
14 Covert the following context Understand This would require the CO 5
free grammar to push down learner to recall the
automata Context Free Grammars and

S aAbB Explain the steps for the

A aB—a conversion of CFG to PDA

B b
Verify the string aab
accepted by equivalent PDA
15 Describe DPDA for L= Understand This would require the CO 5
an bn where n≥1 learner to recall the Push
Down Automata and
Explain the steps for the
construct of the DPDA
16 Describe PDA accepts PDA Understand This would require the CO 5
M for the language learner to recall the Push
L={WWR |W∈{a,b}∗ } Down Automata and
such that L=L(M) Explain the steps for the
construct of the PDA
17 Illustrate PDA M for the Understand This would require the CO 5
language L= {x∈ {a,b}∗ | learner to recall the Push
na (x) > nb (x)} Down Automata and
Explain the steps for the
construct of the PDA.
18 Show that the below Understand This would require the CO 5
languages are deterministic learner to recall the Push
context free languages Down Automata and
L1={0n 1m |n=m and n≥1} Explain the steps for the
L2={on 1m |n=2m and n≥1} checking DCFL or not.
19 Describe deterministic Remember - CO 5
context free languages and
deterministic push down
automata
20 Describe PDA that Understand
This would require the CO 5
recognizes the language learner to recall the Push
L={x=xR : x∈{a,b}+ } Down Automata and
Explain the steps for the
construct of the PDA
PART-C SHORT ANSWER QUESTIONS
1 Differentiate between Understand This would require the CO 5
deterministic and learner to recall the context
nondeterministic PDA. free grammars and Explain
the difference between
DPDA - NPDA
2 Define the concept of PDA. Remember — CO 5

Page 26
3 Describe the concept of Remember — CO 5
NPDA.
4 Define the language of Remember — CO 5
DPDA.
5 Generate CFG for the PDA Understand This would require the CO 5
which accepts the lanuage learner to recall the Push
L={0n 1n | n≥0} Down Automata and
Explain the steps for the
conversion of PDA to CFG
6 Obtain CFG for given PDA Understand This would require the CO 5
M= learner to recall the Push
({q0 , q1 }, {0, 1}, {X, Zo },δ, Down Automata and
q0 , Zo , {}) Explain the steps for the
δ(q0 , 0, Z0 ) = (q0 , XZo ) conversion of PDA to CFG
δ(q0 , 0, X) = (q0 , XX)
δ(q0 , 1, X) = (q1 ,ϵ)
δ(q1 , 1, X) = (q1 ,ϵ)
δ(q1 ,ϵ,X) = (q1 ,ϵ)
δ(q1 ,ϵ,Zo ) = (q1 ,ϵ)
7 Illustrate the processing Understand This would require the CO 5
steps for convertion from learner to recall the Push
PDA to CFG and vice versa. Down Automata and
Explain the steps for the
conversion of PDA to CFG
8 Generate CFG for the Understand This would require the CO 5
non-deterministic PDA learner to recall the Push
which accepts strings that Down Automata and
contain the same number of Explain the steps for the
0s and 1s. conversion of PDA to CFG
9 List out the steps to convert Remember — CO 5
CFG to PDA
10 Describe the acceptance of Remember — CO 5
PDA by final state.
11 Describe the acceptance of Remember — CO 5
PDF by empty stack.
12 Construct a PDA that Understand This would require the CO 5
accepts the language L over learner torecall the Push
{0, 1} by empty stack which Down Automata and
accepts all the string of 0’s Explain the steps for the
and 1’s in which a number conversion of PDA to CFG
of 0’s are twice of number of
1’s.

Page 27
13 Design a non deterministic Understand This would require the CO 5
PDA for accepting the learner to recall the Push
language L ={w w∈{a,b}* | Down Automata and
w contains equal no. of a’s Explain the steps for the
and b’s} conversion of PDA to CFG
14 Construct PDA for the Understand This would require the CO 5
given CFG, and test learner to recall the Push
whether 010000 is Down Automata and
acceptable by this PDA. Explain the steps for the
S  0BB conversion of PDA to CFG
B  0S | 1S | 0
15 Define the PDA and design Remember — CO 5
PDA for L={x∈{a,b}∗ |
na (x) > nb (x)}
16 How push down automata Remember — CO 5
differ from the finite state
automata?
17 Why stack is used in PDA? Remember — CO 5
18 what equivalences of Remember — CO 5
context free language and
pushdown automat
19 Define the PDA acceptance Remember — CO 5
by final state and
acceptance by empty stack
20 How PDA perform Remember — CO 5
acceptance of context free
languages
MODULE V
TURING MACHINE
PART A-PROBLEM SOLVING AND CRITICAL THINKING QUESTIONS)
1 Construct a Turing Machine Apply This would require the CO 6
that accepts the language L learner to recall the
= {a2n bn |n≥0}.Give the Chomsky hierarchy of
transition diagram for the languages and Explain the
Turing Machine obtained. concept of the TM and
Apply the concepts for the
construct of the TM
2 Construct a Turing Machine Apply This would require the CO 6
that gives two’s compliment learner to recall the
for the given binary Chomsky hierarchy of
representation. languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.

Page 28
3 Examine Type 3 and Type Apply This would require the CO 6
2 grammars with example. learner to recall the
Chomsky hierarchy of
languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM
4 Extend the Type 1 and Apply This would require the CO 6
Type 0 grammars with learner to recall the
example. Chomsky hierarchy of
languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.
5 Design a Turing Machine Apply This would require the CO 6
that accepts the set of all learner to recallthe
even palindromes over{0,1} Chomsky hierarchy of
languages and Explain the
concept of the TM and
AApply the concepts for
the construct of the TM
6 Design Turing Machine for Apply This would require the CO 6
L={an bn cn | n=1} learner to recall the
Chomsky hierarchy of
languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.
7 Construct Turing Machine Apply This would require the CO 6
to calculate GCD of two learner to recall the
given numbers Chomsky hierarchy of
languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM
8 Compare and contrast the Apply This would require the CO 6
Finite state machine , PDA learner to recall the
and Turing Machine Chomsky hierarchy of
languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.

Page 29
9 Construct a Turing Machine Apply This would require the CO 6
to accept the following learner to recall the
languages Chomsky hierarchy of
L = { wn xn y n z n | n≥1} languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.
10 Design a Turing Machine Apply This would require the CO 6
that accepts the language learner to recall the
denoted by regular Chomsky hierarchy of
expression (000)* languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.
PART-B LONG ANSWER QUESTIONS
1 Describe short notes on Remember - CO 6
Context sensitive language
and linear bounded
automata.
2 Classify briefly about Understand This would require the CO 6
Chomsky hierarchy of learner to recall the
languages Chomsky hierarchy of
languages and Explain the
all types of languages.
3 Describe a Turing Machine. Remember - CO 6
With a neat diagram
explain the working of a
Turing Machine.
4 Write short notes on the Understand This would require the CO 6
following. a) Chomsky learner to recall the
Hierarchy of Languages b) Chomsky hierarchy of
Linear Bounded Automata languages and Explain the
c) context sensitive differences between TM and
language. other automata.
5 Construct a Transition Apply This would require the CO 6
diagram for Turing Machine learner to recallthe
to accept the language Chomsky hierarchy of
L={w̸=wR | w∈(a+b)∗ } languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM.

Page 30
6 Express short notes on Understand This would require the CO 6
Recursive and Recursively learner to recall the
Enumerable languages. Chomsky hierarchy of
languages and Explain the
Recursive and Recursively
enumerable languages.
7 Describe the properties of Remember - CO 6
recursive and recursively
enumerable languages.
8 Develop a Turing Machine Apply This would require the CO 6
to accept strings formed learner to recallthe
with 0 and 1 and having the Chomsky hierarchy of
set of strings with an equal languages and Explain the
number of 0’s and 1’s. concept of the TM and
Apply the concepts for the
construct of the TM
9 Construct a Transition Apply This would require the CO 6
diagram for Turing Machine learner to recall the
to accept the language L= Chomsky hierarchy of
{wwR | w is any string of 0’s languages and Explain the
and 1’s} concept of the TM and
Apply the concepts for the
construct of the TM
10 Design a Transition table Apply This would require the CO 6
for Turing Machine L= learner to recall the
{an bn cn |n ≥1} Chomsky hierarchy of
languages and Explain the
concept of the TM and
Apply the concepts for the
construct of the TM
11 Construct a Transition table Remember — CO 6
for Turing Machine to
accept the following
language. L = { 0n 1n 0n | n
=1}
12 Construct a Turing Machine Apply This would require the CO 6
that accepts the language L learner to Recall the
= {1n 2n 3n | n ≥1}. Give the Chomsky hierarchy of
transition diagram for the languages and Explain the
Turing Machine obtained concept of the TM and
and also show the moves Apply the concepts for the
made by the Turing machine construct of the TM
for the string 111222333.

Page 31
13 Enumerate Linear bounded Remember - CO 6
automata and explain its
model?
14 Demonstrate the power and Remember - CO 6
limitations of Turing
machine.
15 Construct Transition Remember - CO 6
diagram for Turing Machine
L={anb ncn |n≥1}
16 Construct a Transition Understand This would require the CO 6
diagram for Turing Machine learner to recall the
to implement addition of concept of the TM and
two unary numbers(X+Y). explain the construction of
the transition diagram for
the TM.
17 Construct a Linear Bounded Understand This would require the CO 6
automata for a language learner to recall the
where L= {an bn |n≥1} concept of the LBA and
explain the construction of
the Linear Bounded
automata for the given
language.
18 Classify the types of Turing Understand This would require the CO 6
machines learner to recall the Turing
machines and Explain the
all types of Turing
machines.
19 Describe briefly about the Remember - CO 6
following
a)Church’s Hypothesis
b)Counter machine
20 Construct Transition Understand This would require the CO 6
diagram for Turing Machine learner to recall the
that accepts the language Chomsky hierarchy of
L= {0n 1n 2n | n ≥1 }.Give languages and Explain the
the transition diagram for differences between
the Turing Machine FSM,PDA,TM.
obtained and also show the
moves made by the Turing
machine for the string
001122
PART-C SHORT ANSWER QUESTIONS
1 Describe the Chomsky Remember — CO 6
hierarchy of languages.

Page 32
2 Define Context sensitive Remember — CO 6
language.
3 Describe the Turing Remember — CO 6
Machine
4 Describe the Type 0 Remember — CO 6
grammars .
5 Describe the Type 1 Remember — CO 6
grammars .
6 Describe the Type 2 Remember — CO 6
grammars .
7 Describe the Type 3 Remember — CO 6
grammars
8 List out the types of Remember — CO 6
grammars.
9 Describe the moves in Remember — CO 6
Turing Machine.
10 Define an Instantaneous Remember — CO 6
Description of a Turing
Machine.
11 Describe the Language of Remember — CO 6
Turing Machine.
12 List out types of TMs. Remember — CO 6
13 Differentiate the PDA and Remember — CO 6
TM
14 Describe the multi head Remember — CO 6
Turing Machine
15 Describe the multi Remember — CO 6
dimensional Turing
Machine.
16 Describe the multiple tapes Remember — CO 6
Turing Machine.
17 Describe the recursive Remember — CO 6
languages
18 Describe the recursively Remember — CO 6
enumerable languages.
19 Describe the two way Remember — CO 6
infinite Turing Machine.
20 Describe the the non Remember — CO 6
deterministic Turing
Machine.
21 Describe the Turing Understand — CO 6
Machine for 1’s complement
for binary numbers.

Page 33
22 Describe the Recursive Remember This would require the CO 6
languages and Recursively learner to recall the
enumerable languages. concept of the TM and
explain the construction of
the TM.
23 Define Church’s Hypothesis Remember — CO 6

Course Coordinator: HOD-IT


Dr.U.Sivaji, Associate Professor

Page 34

You might also like