WBUT Question Papers CS Formal Language And Automata Theory B Tech Forth Sem June 2008

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

<v

Qa

0

Q4

1

Q3

*

Qi

0

q4

0

Q4

q3

* . 1

Qa

1

 

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

Leave a Comment