# Bharati Vidyapeeth 2008-1st Sem B.Tech Information Technology t tech it - Question Paper

Friday, 18 January 2013 08:35Web

GANGOTRI V(2004 COURSE):OCT/NOV 2008

THEORY OF COMPUTER SCIENCE

• ANSWER 3 ques. FROM every part

part I

1)

**a)**If L1 and L2 are bot regular language over alphabet ? the prove that L1+L2, L1.L2, L* are also regular.

**b)**describe the following:

**i)**d* for NFA

**i**e closure of set of states

**i)****i**Relation

**i****i)****i**Transition graph

**v)**2)

**a)**Let L = {x ? {0,1}|x ends in one and does not contain substring 00}

i)Contruct a regular expression

ii)Contruct NFA for (i)

**i**Cnvert the NFA to DFA

**i****i)**3)

**a)**obtain CFG with no useless symbols

S->AB|CA

B->BC|AB

C->aB|b

A->a

**b)**construct a PDA that accepts a language by the CFG “S->S+S|S*S|4

**c)**state the rules of replacement in NFA

4)

a)show that

i) (a*b*)=(a+b)*

ii) (ab)*a=a(ba)*

part II

5)

a)Give the formal definition of PD

**A.**discuss the transition function.

**b)**design a PDA that acceptsthe language L of all balanced strings involving 2 kinds of brackets “{}”

and “[]”

6)

**a)**design a PMT systemfor generating palindromes over {0,1,2}

**b)**provide the properties of recursive and recursively ennumerable sets

7)create a TM that creates the copy of its input string. provide the ID of any string. Show the configuration at

every step.

8)Write any three.

i) Allpications of PDA

ii) Solvability and semisolvability

iii) Multistack turing machine

iv) Type 0 and kind one grammar

Earning: Approval pending. |