WBUT Exam Papers CS Formal Language And Automata Theory B Tech Sem Forth 2011
WBUT Exam Papers CS
Formal Language And Automata Theory B Tech Sem Forth 2011
Time Allotted : 3 Hours
Full Marks : 7
The figures in the margin indicate full marks. Candidates are required to give their answers in their own words
as far as practicable.
GROUP – A ( Multiple Choice Type Questions )
1. Choose the correct alternatives for the following : 10 x 1 = 10
i) Moore machine output depends on
a) input
b) input and present state
c) present state
d) none of these.
ii) FSM can recognize
a) a grammar dependent on characteristic of FSM
b) on CFG
c) any unambiguous grammar
d) only regular grammar.
iii) DFA has a transition function
a) QxXtoQ b) QxIto2<2
c) both (a) and (b) d) none of these.
iv) The class of CFG is not closed under
a) concatenation
b) intersection
c) union
d) repeated concatenation.
v) Consider the CFG
X > zX/bX/a Y +Ya/Yb/b
Any string of terminals, which can be generated by the CFG .
t
a) has at least one b
b) ends with a
c) has no consecutive a’s or b’s
d) has at least 2 a’s.
vi) A grammar that produces more than one parse tree for some sentence is said to be
a) contiguous b) ambiguous
c) unambiguous cl) regular.
)01 o
vii) The following production rules of a regular grammar generates a language L
S aS / bS / a / b
The regular expression for L is
^{3) }^{a + b} b) fa + £>)”
c) (a _{+} fc)(_{a + b)}* _{d) (aa + bb)a}y
viii) If Q is the number of states in the NFA, the equivalent DFA can have maximum number of states –
a) ^{Q} b) Qi
^{c}) ^{2<}?~ ^{1} d) 2Q.
ix) A CFG, S > aS/bS/a/b, is equivalent to
*
^{a) (a + fc,+} b) (a _{+} b)(a _{+} b{
t ‘
^{c) }
(a + b) (a + 6) _{d)} all of these.
x) A Push down automaton is different from a finite automaton because of
a) a read head
. ‘ • i
b) a memory in the form of stack
c) a set of states
d) all of these.
[ Turn over
GROUP B ( Short Answer Type Questions )
Answer any three of the following. 3×5= 15
£
 Convert the following Contextfree grammar into an equivalent grammar in CNF
S > IA/0B A > 1AA/0S/0 B +0BB/1S/1
 Is the following machine information lossless ? If yes, find the order of losslessness.
PS  NS, z  
x=o  X= 1  
A  A, 0  B, 0 
B  C, 0  D, 0 
C  D, 1  C, 1 
D  B, 1  A, 1 
 Let G be the grammar
S » aB/ba, A^a/aS/bAA, B+b/bS/aBB For the string aaabbabbba , find
a) leftmost derivation
b) rightmost derivation
c) parse tree. .
 Construct a Turing machine that accepts all strings over
i
{ 0, 1 } with an even number 0’s and even number of l’s.
 Test whether the following machine is definite or not
i) by using synchronizing tree
ii) by using repeated derivation of contracted table
iii) if the machine is definite,
what is the order of definiteness ? Justify.
Present State  Next State  
a = 0  a = 1  
A  A  B 
B  C  B 
C  A  D 
D  C  B 
GROUP C ( Long Answer Type Questions )
Answer any three of the following. 3 x 15 = 45

a) Construct a DFA diagram from the NFA given below :
c) What are Kleene Closure and Positive Closure ? Give example for both. 2+1
8, a) What do you mean by Disginghishable and Indistinguishable state ? , 3
b) Use Myhill Nerode Theorem to minimize the following finite automata : ? 12
 a) Give the Regular Expression for the DFA using Arden Theorem
5
b) What is Griebach Normal Form (GNF) for Context Free grammar ? 1+4
Convert the following grammar into GNF
S > ABb/a
A aaA / B
B > bAb
c) Using Pumping Lemma show that L = {a^{n}b^{n} : n > 0} is not regular. 5
CS / B.TECH (CSE) / SEM4 / CS401 / 2011  
10. a)  Construct a NFA with _{E} or X transition  for 
r = (11 + 0)‘(00 + 1)*.  5  
b)  What is PDA ?  5 
c)  Construct PDA for L = {unv : w belongs to (0,1) }.  5 
11. a)  What do you mean by kequivalent states ?  3 
b)  Draw the Merger graph, Merger table, Compatibility  
graph and then minimize the following :  12 
Present State  Next State, o/p  
i/p = 0  i/p = 1  i/p =2  i/p ~ 3  
A  —  C, 1  E, 1  B, 1 
B  E, 0  —  —  
C  F, 0  F, 1  —  
D  B, 1  —  
E  F, 0  A, 0  A l  
F  C, 0  —  B, 0  C, 1 
f 
Recent Comments