[Link].
com
[Link]
Name : …………………………………………….………………
Roll No. : …………………………………………...……………..
Invigilator’s Signature : ………………………………………..
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
2012
FORMAL LANGUAGE & AUTOMATA THEORY
Time Allotted : 3 Hours Full 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 × 1 = 10
i) The basic limitation of FSM is that
a) it can’t remember arbitrary large amount of
information
b) it sometimes recognize grammar that is not regular
c) it sometimes fails to recognize grammar that is
regular
d) all of these.
4358 [ Turn over
[Link]
[Link]
[Link]
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
ii) Choose the correct statements :
a) Moore & Mealy machine are FSM with output
capabilities
b) Any given Moore machine has an equivalent Mealy
machine
c) Any given Mealy machine has an equivalent Moore
machine
d) Moore machine is not an FSM.
iii) The intersection of CFL & regular language
a) need not be regular b) need not be CF
c) is always regular d) none of these.
iv) Palindromes can’t be recognized by any FSM because
a) an FSM can’t be remember arbitrary large amount
of information
b) an FSM can’t deterministically fix the mid point
c) FSM can’t find whether 2nd half of the string
machines the 1st half or not
d) None of these.
v) Can a DFA simulate NFA ?
a) no b) yes
c) some times d) depends on DFA.
4358 2
[Link]
[Link]
[Link]
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
vi) ( P + Q )* = ?
a) ( P* + Q* ) b) P* + Q*
c) ( P* Q* )* d) both (a) and (c).
vii) What is the RE for the language set strings with atleast
one 1, one 2 and one 3 ?
a) 1+2+3 b) 11* 22* 33*
c) 1* 2* 3 d) both (a) and (b).
viii) Which of the following sets is regular ?
a) { ai : i = n2, n > = 1 }
b) { ap : p is prime }
c) { ww : w is in (a, b) + }
d) { a2n : n > = 1 }.
ix) The regular expression representing the set of all strings
over { x, y } ending with XX beginning with Y is
a) XX ( X + Y ) * Y b) YY ( X + Y ) * X
c) Y ( X + Y ) * XX d) Y ( XY ) * XX.
x) Regular expression (a/b)(a/b) denotes the set
a) { a, b, ab, aa } b) { a, b, ba, bb }
c) both (a) and (b) d) none of these.
4358 3 [ Turn over
[Link]
[Link]
[Link]
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
GROUP – B
( Short Answer Type Questions )
Answer any three of the following. 3 × 5 = 15
2. Show that L = { On 1n|n > = 1 } is not regular.
3. Write the CFG for the following language
L = { 0i 1j 2k|I = j j = k }
4. Design a PDA which accepts the language
L = { w ∈ (a,b)*|w has equal no. of a & b }.
5. a) Give DFA which reads strings from {a,b} and with aaa. 3
b) Construct a DFA equivalent to M = { {q0, q, }, {0, 1}, δqo,
{q0}}, δ is given by the state table.
State / 0 1
q0 q 0 q 1
q1 q1 q0, q1 2
6. Find a GNF grammar equivalent to the following CFG :
A1 → A2 A3
A2 → A3 A1|b
A3 → A1 A2|a
GROUP – C
( Long Answer Type Questions )
Answer any three of the following. 3 × 15 = 45
7. a) Construct a DFA diagram to the NFA given below. 6
4358 4
[Link]
[Link]
[Link]
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
b) Convert Mealy Machine to Moore Machine. 6
c) What are Kleene Closure and Positive Closure ? Give
example for both. 2+1
8. a) What are distinguishable and Indistinguishable state ? 3
b) Use Myhill Nerode Theorem to minimize the following
finite automata. 12
4358 5 [ Turn over
[Link]
[Link]
[Link]
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
9. a) Give the Regular Expression for the DFA using arden
Theorem. 5
b) What is Griebach Normal Form (GNF) for Context Free
grammar ?
Convert the following grammar into GNF
S → ABb/a
A → aaA/B
B → bAb 1+4
c) Using Pumping Lemma show that L = {anbn : n > = 0} is
not regular. 5
10. a) Construct a NFA with ε or λ transition for
r = (11 + 0)*(00 + 1)* 5
b) What is PDA ? 5
c) Construct PDA for L = {wwR : w belongs to (0, 1)* } 5
4358 6
[Link]
[Link]
[Link]
CS/[Link](CSE/IT)NEW/SEM-4/CS-402/2012
11.
PS NS, Z
I1 I2 I3
A C,O E,1 ….......
B C,O E,… ………
C B,… C,O A,…
D B,O C,… E,…
E …… E A,…
For the incompletely specified machine shown above
find the minimum state reduced machine containing the
original one. 8
PS NS,Z
x=0 x=1
A B, 1 H, 1
B F, 1 D, 1
C D, 0 E, 1
D C, 0 F, 1
E D, 1 C, 1
F C, 1 C, 1
G C, 1 D, 1
H C, 0 A, 1
Using this table
a) Find the equivalence partition. 3
b) Find the standard form of the corresponding
reduced machine. 3
c) What is the minimum length sequence that
distinguishes state A from state B ? 1
4358 7 [ Turn over
[Link]