My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Download Model question papers & previous years question papers
|
Posted Date: 06 Dec 2008 Posted By: SHAHZAD ADIL Member Level: Silver
|
2008 Bharati Vidyapeeth B.Tech Information Technology t tech it sem 1 University Question paper
GANGOTRI V(2004 COURSE):OCT/NOV 2008
THEORY OF COMPUTER SCIENCE
• ANSWER THREE QUESTIONS FROM EACH SECTION
SECTION 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) Define 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 1 and does not contain substring 00}
i)Contruct a regular expression
ii)Contruct NFA for (i)
iii) Cnvert the NFA to DFA
3)
a) find 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)*
SECTION II
5)
a)Give the formal definition of PDA. Explain the transition function.
b) design a PDA that acceptsthe language L of all balanced strings involving two types of brackets “{}”
and “[]”
6)
a) design a PMT systemfor generating palindromes over {0,1,2}
b) give the properties of recursive and recursively ennumerable sets
7)create a TM that creates the copy of its input string. Give the ID of any string. Show the configuration at
each step.
8)Write any three.
i) Allpications of PDA
ii) Solvability and semisolvability
iii) Multistack turing machine
iv) Type 0 and type 1 grammar
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
Advertise Here
|