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 By: vivekanandan Member Level: Gold Posted Date: 18 Jun 2008
|
2006 2006 Anna University B.E COMPUTER SCIENCE THEORY OF COMPUTATION Question paper Question paper
ANNA UNIVERSITY :: CHENNAI – 600 025
FIFTH SEMESTER
B.E. COMPUTER SCIENCE AND ENGINEERING
CS332 - THEORY OF COMPUTATION
TIME: THREE HOURS MAXIMUM : 100 MARKS
ANSWER ALL QUESTIONS
PART A – (10 X 2 = 20 MARKS)
1. What is the difference between DFA and NFA?
2. Give regular set for the following expression: 1(01)*(10)*1
3. For the grammar G defined by S->AB, D->a,A->Aa,A->bB,B->Sb, give derivation tree for the sentential form babab
4. Give pumping lemma to prove that given language L is not context free.
5. Give formal definition of PDA.
6. Give an example of a language accepted by a PDA but not by DPDA.
7. Prove that the function f(n)=n-1 is computable.
8. Design a Turning machine to compute n mod 2.
9. What is undecidability?
10. Differentiate between recursive and recursively enumerable language.
PART B – (5 x 16 = 80 MARKS)
11. Construct a context free grammar for the given language L={anbn|/n>=1}U{amb2m/m>=1} and hence a PDA accepting L by empty stack (16)
12.a) Prove the equivalence of NFA and DFA. (8)
b) Prove that a balanced parenthesis is not a regular language. (8)
(OR)
12.a) Explain in detail with an example the conversion of NDFA to DFA (8)
b) Show that L = {an! : n>=0} is not regular. (8)
13.a) Explain in detail the ambiguity in context free grammar. (8)
b) Convert the grammar S->ABb|a, A->aaA|B, B->bAb into greibach normal form. (8)
(OR)
13.a) Construct a context free grammar for the languages L(G1)={aib2i/I>0} and L(G2)={anban/n>0} (8)
(b) Prove that {op | p is prime} is not context free. (8)
14. Construct a Turing Machine to do the proper subtraction (16)
(OR)
14.a) Construct a Turning machine to perform multiplication (8)
b) Prove the equivalence of two-way infinite tape with standard Turing machine. (8)
15.a) Discuss in detail about universal Turing machine. (8)
b) Prove that halting problem is undecidable. (8)
(OR)
15.a) Prove that the union and intersection of two recursive languages are also recursive. (8)
b) Prove that there exists an recursively enumerable language whose complement is not recursively enumerable. (8)
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.
|
Watch TV Channels
|