West Bengal Institute of Technology (WBIT) 2008-4th Sem B.Tech Computer Science and Engineering Computer Science - Formal Language and Automata Theory - Question Paper

I /

C8/B.TBCH (CU)/SBlf-4/CS-401/06    3

ENGINEERING & MANAGEMENT EXAMINATIONS, JUNE - 2008 FORMAL LANGUAGE AND AUTOMATA THEORY SEMESTER-4

Time: 3 Hours]    [ Full Marks : 7C

GROUP-A (Multiple Choice Type Questions)    .

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

. _

I)    Which of the following regular egressions 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)    DFA has

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.

* . ill) 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,

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

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

j ' .

c) recursion    d) iteration.

\W4U6li (iKT

. . . \

' V \

C8/B.TBCH (C8E)/8BM-/CS-01/08    4

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

a)    concatenation b) mnn

c) intersection    d) repeated concatenation. I_I

vi)    The grammar Q * ({S}, {0,1}, P,S) where P={S0S1, SOS, S-*S1, S-i-0} is a ' a) recursively enumerable language

b)    regular language

c)    context sensitive language

d)    context free language.    _

vli) If S is the number of states in NDFA then equivalent DFA can have maximum of

a) S states    b) S-l state

c) 2^s states    d) 2^s -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 hipest 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

IIV-344811113)1

(Short Answer Type Question* )

Answer any three of the following.

₂. a) What do you mean by a subtree of a derivation tree ?

q __AS/a A - SbA/SS/ba. Show that

b) Consider O whose production, are S - aAS/a, A

_s_ aabbaa by construct a dertvatton tree, by right most derivation, whose

2 + 3

yield is aabbaa.    .

	Next State	i/p=0	Next state	1 i/p=l 1 -1
Present State	State	Ootpitt	State	! Output |
Qi	Q*	1 ' 1	Q*	0
Qa	q3	0	Q4	1
- Qs *	Qi	0	Q4	0
Q4	q3	* . 1	q2	1

Reduce the following grammars to GNF : _S - AO. A - OB. B - OA. B - 1

The set L a ,aVc /where i. * are integer and i.k ,1). Is L regular 7 Justly your

, answer.

CS/B.TBCH (C8E)/8EM-4/CS-U>l /OS    6 .

6. Minimize the following machine by determining the set of equivalent states.

Present State	Next State	i/p=o	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 \	B	0
F	E	1	D	0
O	D	0	G	0
- H	F	. 1	B	-o

-    GROUP-C

(Long Answer Type Question* )

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

7. a)    State & discuss Myhill-Nerode theorem.    5

b)    Write the CFG for the language

.    L { 0* 1^J 2^k | iJ or Jk).    .    5

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

/)

/yCS/B.TKCH (CSE)/MtM-*/C8-401/0>

8 _{a} 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 = {a" bⁿ | n * 0 }. Find a CFG to generate L².    ^{3 + 2}

c)    Design a PDA which accepts the language.

5

L * { W t (a,b)* 1IV 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

9

specified machine.

PS	Ii	NZ, Z U	Is
A	C. 0	E. 1	-
B	C. 0	E,-	-
C	B,-	C, 0	A,-
D	B. 0	C,-	E,-
E		E, 0	A.-

/

CS/B.TECH [CSBJ/BBH-t/CS-401 /OS    8    ! Ilffflil ! PS	x=0	, NZ.Z x=l
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.    7

b) Find the minimal Inverse machine of the FSM in problem ( a ).    8

11. 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 ORqi - Qa bRqg OL q2 !LQqa q3 - bRq4 bRqs Q4 0Rqs 0Rq4 lRq4 Qs 0Lqa - -

END

I1V-2448111D0

Attachment: west-bengal-institute-of-technology--wbit--2008-b-tech-computer-science-and-engineering-51964-1.pdf

Earning:   Approval pending.