# WBUT Question Papers CS

## Formal Language And Automata Theory B Tech Forth Sem June 2008

Time: 3 Hours]

[ Full Marks : 7C

GROUP-A

(Multiple Choice Type Questions)       .

1. 1.                                                                                                                                                                                                                                                                                      Choose the correct alternatives for the following :                 10×1 = 1C

1) Which of the following regular expressions over { 0, 1 } denotes the set of all strings not containing 100 as a sub-string?

a) 0*(1*0)*               b) 0*1010*

c)          0*1*01*               d) 0*(10+1) *.

ii)         DPAhas

a)         single final state ‘

b)         more than one initial states

*   c) . unique path (for a set of inputs ) to the final state

d)         all of these.                                  h—–

iii)        Which of the following is regular ?

a)         Strings of 0’s whose length is a perfect square

b)         Strings of all palindromes made up of 0’s & l ‘s

c)          Strings of 0’s, whose length is a prime number

d)         Strings of odd number of zeroes.               L—

iv)        The logic of pumping lemma is a good example of

a) the pigeon-hole principle    b) the divide & conquer technique

c)   recursion                 d) iteration.                          L——

|W:g446ii (l*n

v)          The class of context free language Is not closed under

a)          concatenation b) mn«n c) Intersection______________ d) repeated concatenation. I I

vi)           The grammar Q * ({S}, {0,1}, P,S) where P={S—0S1, S—OS, S-*S1, S—0} is a ‘ a) recursively enumerable language

b)         regular language

c)          context sensitive language

’if 1

d) context free language.

vii)       If S is the number of states in NDFA then equivalent DFA can have maximum of a) S states   b) S -1 state

c) 2s states              d) 2s -1 states.          1

viii)      If LI is the set of languages Accepted by a NPDA and L2 is the set of context free languages, then

a)      L1=L2    b) L1CL2

c) L2QL1                   d) None of these.        1 I

ix)        What is the highest type number to the grammar given by the following production rules

S -* Aa, A -* c | Ba, B-*abc

a)     zero b) one

c)  two  d) three. . ,                                                            i

x)         Given an arbitrary NDFA with n states, the maximum number of states in an equivalent minimized DFA is at least

a)

n° * b) 2”c)     n !                      d) • None of these.                          1                        J

11V-244811 TOJl

(Short Answer Type Questions )

Answer any three of the following.

1. 2.               a) What do you mean by a subtree of a derivation tree ?
2. c _ a AS/a A – SbA/SS/ba. Show that

b)          Consider G whose productions are S – aAS/a. A

s_ aabbaa hy construct** a derivation tree, by r,gh. most der.va.lon. whose

2 + 3

yield Is aabbaa.

 Convert the Mealy Machine ( given below) to a Moore 1 Machine. 5 ———— ——— 1 Next State i/psO Next state l/p=l ________________ Present Stste State Output State Output Qi Qa ■ \ ■ 1 Qi 0

Reduce the following grammars to GNF :

S -* AO. A – OB. B – OA, B – 1

The set L * (aVc‘ /where U. – are mteger and k * 1). .s I- regular ? Justdy your

1 + 4

answer.

itv^uanCTl

1. Minimize the following machine by determining the set of equivalent states.
 Present State Next State i/p=0 Next state i/p=l State Output State Output A E 1 C 0 B C 0 A 0 C B 0 G 0 D G 0 A 0 E F 1 V B 0 F E 1 D • 0 G D 0 G 0 H F . 1 B 0

GROUP -C ( Long Answer Type Questions )

Answer any three of the following questions.                       3×15 = 45

1. a)                                                                       State & discuss Myhlll-Nerode theorem.       5

b)          Write the CFG for the language

.       L= {O’ 1J 2k|i=JorJ*k}. .                                                                                                     5

c) Prove that CFLs are not closed under Intersection and complement operation.      5

nv-2446ii (i*)

TECH (CM)/MM-4/C»-401/0«

E – E+E | E*E | a. Prove that the CFG with this production rule Is ambiguous.

2  + 3

Remove the ambiguity from this grammar.

b)          S-*AB;A-*a. B – C/b. C – D; D – E. E – a.

remove the unit production.

L = fan bn | n a 0 }. Find a CFG to generate L2.

c)          Design a PDA which accepts the language.

5

L = { W e (a.b)* | W has equal no. of a & b}.

9. a) A long sequence of Input pulses enters a two-input, two-output synchronous sequential circuit, which is required to produce an output pulse Z=l. whenever a

sequence 010101 occurs. Overlapping sequences are accepted. Draw the state

. 6 transition diagram.

b) Find minimum state reduced machine containing the following incompletely

specified machine.

 PS Ii NZ. Z I2 I3 A C. 0 E. 1 – B C. 0 E.- – C B,- C. 0 A,- D B. 0 c.- E, – E E. 0 A.-

iiy.244an am

8

10. a) Show that the following FSM is Information lossless of finite order :

 PS x=0 . NZ.Z x= 1 A C. 0 D. 1 B D, 0 C, 1 C A, 0 B. 0 D C. 1 D. 1

Also find Its order of Information losslessness.

Find the minimal Inverse

machine of the FSM In problem ( a ).                                                                       8

1. a) What do you mean by Inverse machine ? Write the definition of a lossless machine. What do you mean by Halting problem of a Turing machine ? Why a Turing machine is called linear bounded Automata ?                                                                                  2 + 2 + 2 + 2
b) Consider the Turing machine’s description is given in table below. Draw the computation sequence of the input string 00.                                                            7

 Present state Tape symbol:: b Tape symbol:: 0 Tape symbol:: 1 Qi lLq2 ORq, – Qa bRq3 0L q2 lLQqa q3 – bRq4 bRqs Q< 0Rq5 0Rq4 lRq4 Qs 0Lq2 – –

nv-2448iiirar