West Bengal Institute of Technology (WBIT) 2010-4th Sem B.Tech Computer Science and Engineering Computer Science - Formal Language and Automata Theory - Question Paper
Name :....................................................;...............
RoUNo. : .......... ......... ...........*.....
Invigilator's Signature:...............................................
CS/B.TECH(CSE)/SEM-4/CS-401/2010
2010 FORMAL LANGUAGE AND AUTOMATA THEORY
Time Allotted : 3 Hours FuU Marks - 70
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
1) The production grammar { S > aSbb, S -> abb} is
a) type-3 grammar b) type-2 grammar
c) type-1 grammar d) type-0 grammar,
ii) The loop-free testing graph indicates that
a) the machine has finite memory ,
b) the machine has non-flnite memory
c) the machine has finite states
d) the machine has non-flnite states.
CS/B.TECH(CSE)/SEM-4/CS-401/2010
a) Mealy M/c b) Moore M/c
c) Turing M/c d) All of these.
iv) Consider the following regular expression :
R = (ab + abb) *bbab. '
Which of the following is not in the set denoted by R ?
a) ababab b) ababbabbbab
c) abbbab d) abbabbbab.
v) Which of the following is correct ?
a) Language can be derived from the FA
b) Regular expressions can be derived from the FA
c) FA can be derived from the language
d) Both (a) & (b).
vi) The reduced grammar of S - AB | a, A - a is
) S-> a b) S-> a\A
A~> a A -> a
vii) Which of the following grammars generates strings with any number of ls ?
/
h) S > I S, S > e d) (b) & (c).
a) S - 1A, A -> e
viii) Input sequence of an information lossless machine can be determined from the knowledge of
.
a) only output sequence
b) output sequence and initial state
c) output sequence, initial state and final state
d) initial state.
ix) Context Free Grammar can be recognized by
a) finite state automata
b) 2-way linear bounded automata
c) push-doftn automata dj both (b) & (c).
x) Which of the following statements is wrong ?
a) A turing machine cannot solve halting problem.
b) Set of recursively enumerable languages is closed under union.
c) A finite state machine with 3 /stacks is more powerful than finite state machine with 2 stacks.
d) Context sensitive grammar can be recognized by a linearly bounded memoiy machine.
GROUP - B ( Short Answer Type Questions )
Answer any three of the following. 3 x 5 = 15
2. a) State the pumping lemma for regular language, 2
b) Using pumping lemma prove that the set L = {0 41 4 | (i 1} is not regular. 3
3. Draw the transition diagram of a finite state automaton that accepts all strings over { 0, 1 }
a) having odd number Of 0's
b) having even number of 0's and even number of l's.
4. Convert the following context free grammar into an equivalent grammar in CNF :
S > aAbB .
A -> abAB / aAA / a
B-> bBaA / bBB/b.
5. State and discuss Myhill-Nerode's theorem. .
' . . / . .
6. Construct a regular grammar G generating the regular set represented by
P= a*b ( a + b ).
CS/B.TECH(CSE)/SEM-4/CS-40l/2010
GROUP- C f1'00* Answer Type Questions)
Answer any three of the following. 3 x 15 = 45
7. a) State the dlflFerence between DFA and NFA. 2
b) Design an NFA which accepts set of all binary strings containing 1100 or 1010 as substrings. 3
c) What is Regular language ? 2
d) Find Regular expressions over 2 = { a, b } for the languages defined as follows :
D LI ={ am bm : m > 0 )
L2 = {a*nb*"+> I n20.mn*6}
iii) L3 = {bmabn: m > 0, n > 0 } 1 + 1 +l
e) Find the Regular expression for the following transition graph :
CS/B.TECH(CSE)/SEM-4/CS-401/2010
8. a) Define pushdown automata. 2
b) Construct a PDA accepting the set of all strings over { a, b} with equal number of a's and bs. 5
c) What are the nonempty transitions in an NPDA ? 2
d) Let G be a grammar s -> OB | 1A, A - 0 | OS | 1AA, B -> 1 | IS | 0BB. For the string 00110101, find
i) leftmost derivation
ii) rightmost derivation
; -
iii) derivation tree. 2 + 2 + 2
9. a) Construct the minimum state automata equivalent to
given automata M defined below :
|
'statesN,*N*N |
a |
b |
|
-*9o |
9s |
9i |
|
Qi |
92 |
9e |
|
*<?2 |
92 |
9o |
|
<?4 |
9s |
97 |
|
9e |
92 | |
|
<?6 |
Q4 |
w |
|
97 |
92 |
q6 |
( * q2 indicates that q2 is the final state ) 6
CS/B.TECH(CSfD)/SEM-4/CS-401/2010 b) Convert the following NFA to DFA. 5
c) Prove that CFLs are not closed under Intersection and complement operation. 4
10. a) What is information lossless machine ? 3
b) Consider the machine shown in the following tahi*
Is this machine Information lossless of finite order ? If yes, find the order ji. g
c)
Design a 2-input 2-output Mealy machine, which takes as input a binary stream and generates on output of 1 only when a sequence of the pattern 01011 is found in the input stream. Design should be clearly justified. 7
|
11. a) Consider the following machine : | ||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||
i) Draw the merger graph. 2
ii) Draw the merger table. 2
iii) Draw the compatibility graph. 2
iv) Find the minimal closed covering with justiflcation.
3
|
b) Consider the machine given below : | |||||||||||||||||||||||||||||
|
Derive the closed partitions. Construct a n-lattlce for It.
4001 8
|
Attachment: |
| Earning: Approval pending. |
