WBUT Question Papers CS
Formal Language And Automata Theory B Tech Forth Sem
Time : 3 Hours J
[ Full Marks : 70
GROUP – A
 Choose the correct alternatives of the following : 10 xl» 10
U L* { a^{n} b^{n} c^{n} , where ne l}ts
a) regular
b) context free but not regular
c) context sensitive but not context free
d) none of these.
11) Which Is true of the following ?
a) Merger graph is a directed graph
b) Compatible graph is a directed graph
c) Both are directed
d) None of these.
in) The Intersection of a CFL and regular language is
a) context free
b) regular but not context free
c) neither context free nor regular
d) both regular and context free.
iv) a* ( a + b) * is equivalent to
^ 1— i + b
c) a* b* d) None of these.
a) S> aA b) SA > AS
c) S >AB d) All of these.
vl) Context free language are not closed under
a) union ? b) complementation
c) concatenation : d) star closure.
vii) Which is more suitable for an*Ambiguous Grammar 7
a) All ambiguities can be removed . ‘
b) Ambiguity can be removed by setting priority
c) Only inherent ambiguity can be removed
d)There is no suitable rule for removing ambiguity.
viii) Merger table is a substitute of
a) Merger graph b) Compatible graph
c) Minimized machine d) Finite state machine.
ixj DFA converted from an NFA with n states can have maximum
a) n states b) n ! states
c) 2^{n} states d) ^{n}C_{2} states.
x) The accepting automata for the context sensitive language Is
a) linear bounded automata b) finite automata
c pushdown automata d) all of these.
4401 (04/deT
GROUP B ( Short Answer Type Questions )
Answer any three of the following. 3×5= 15
 In response to an unknown input sequence, the machine given below produces the output sequence 1110000010. Find the input sequence to the machine if it is known that its initial state is A and final state is F. 5
PS 
NS. z 

X
II o 
x = 1  
A 
B. 1  C, 0 
B 
D. 1  B. 1 
C  E. 1  B. 0 
D 
A, 0  E. 0 
E 
F. 0  D. 1 
F 
D. 0  A, 1 
 What is the basic difference between Mealy machine and Moore machine ? Construct
t
a Mealy machine which is equivalent to the Moore machine given below : 2 + 3
PS 
NS 
Z 

x=0  X — 1  
<*0  Si  ^ 2  1 
^3  <*2  0  
<*2  ^2 
1 

<*3  ^0  *3 
1 
 Show that L = { a^{p}  p is prime } is not regular. 5
 Let G be the grammar S aaabbabbba find a.
a) leftmost derivation
b) rightmost derivation
c) parse tree.
6 Is the following machine Information lossless ? If yes. find the order of losslessness.
4 + 1
PS 
NS, z 

x = 0  x = 1  
A 
A, 0  B. 0 
B 
C. 0  D. 0 
C 
D. 1  C. 1 
D 
B. 1  A, 1 
GROUP C ( Long Answer Type Question! )
Answer any three of the following.
State the difference between DFA and NFA.
Design an NFA which accepts set of all binary strings containing 1100 or 1010 as substrings.
What is regular language ?
Find regular expressions over I = { a, b} for the languages defined as follows :
I) LI = { a^{m} b^{m} : m > 0 }
II) L2 = { a^{2n} b^{2m}* ^{1}  n^O, mniO) ill) L3 = {b^{m}ab^{n}: m>0, n>0}
Present 
VP 
0 
Up 
.1 
State 
Next State 
o/p 
Next State 
o/p 
A 
E 
0 
D 
1 
B 
F 
0 
D 
0 
C 
E 
0 
B 
1 
D 
F 
0 
B 
0 
E 
G 
0 
F 
1 
F 
B 
0 
C 
0 
G 
C 
1 
H 
0 
H 
A 
1 
G 
0 
d) Give definition of lossy and lossless machine. 
10 Draw the merger graph, merger table, compatibility graph and then minimize the
4 + 4 + 3 + 4
Present State 
Next State, o/p 
Next State, o/p 

t/p = 0 
t/p= 1 
i/P – 2 
t/p = 3 

A 
— 
C. 1 
E. 1 
B. 1 
B 
E. 0 
– 
– 
– 
C 
F. 0 
F,. 1 
— 
1 
D 
— 
– 
B. 1 
– 
E 
— 
F. 0 
A, 0 
D. – 
F 
C. – 
— 
B. 0 
C. 1 
Convert grammars to Greibach Normal Form ( GNF ). 
I) S > aSa  aSb  e
II) S » aSB  aSbS  e .
Find a reduced grammar equivalent to the grammar S > aAa, A > bBB, B > ab. C* aB.
Explain the concept of 2way finite automata. 5 + 6 + 4
END