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

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
ii) e closure of set of states
iii) Relation
iv) Transition graph
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)
iii) Cnvert the NFA to DFA
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 PDA. 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.