Download Model question papers & previous years question papers
Posted Date: 26 May 2010 Posted By:: Vijay Kumar Vishwakarma Member Level: Gold Points: 5 (₹ 1)

2009 Tamil University B.E Computer Science and Engineering Model question paper  2009 Question paper
SUBJECT : Theory of Computation SUBJECT CODE: CS1303 SEMESTER : 5th YEAR : III TIME : 3Hrs Total Marks :100
PART A (10*2=20) 1. What is the difference between NFA and DFA? 2. Define eclosure of a State 3. For the grammar S?A1B,A?0A/?,B?0B/1B/?,give leftmost and right most derivation for the string 00101. 4. Construct CFG to generate {anbn /n?Z+} 5. Is it true that deterministic push down automata and non deterministic push down automata are equivalent in the sense of language of acceptances? 6. Define instantaneous description of a PDA 7. Define basic Turing machine. 8. Explain multitape Turing machine model 9. When a problem is said to be un decidable? Give an example of an undecidable problem. 10. Show that the union of recursive language is recursive.
PARTB(5*16=80) 11. (a) (i) Prove that language L is accepted by some NFA if and only if L is accepted by some DFA . (8) (ii) Consider the following ?NFA .Compute the closure of each state and find its equivalent DFA.
? a B c p {q} {p} ? ? q {r} ? {q} ? *r ? ? ? {r} Or (b) (i) P rove that a language L is accepted by some DFA iff L is accepted by some NFA. (ii) Convert the following NFA to its equivalent DFA.
0 1 p {p,q} {p} q {r} {r} r {s} ? *s {s} {s}
12. (a) (i) Construct an NFA equivalent to the following regular expression ((10)+(0+1))*01. (ii) Check whether the language L={ 0n2/n?Z+ } is regular or not? (Or) (b) (i) Construct DFA equivalent to the NFA given below 0 1 ?p {p,q} {p} q {r} ? *r ? ?
(ii) Prove that if L=L(A) for some DFA then there is a regular expression R such that L=L( R). 13. (a) (i) Prove that if L is a contextfree language then there exists a PDA such that L=N(M). (ii) Explain different types of acceptance of a PDA .Are they equivalent in sense of language acceptance? Justify your answer. (or) (b) If L is N(M) for some PDA M ,then prove that L is context free language
14. (a) (i) Design a TM to accept the language L= { anbn /n?Z+} (ii) Explain with an example how finite control of a TM can be used to hold a finite amount of information. (Or) (b) (i) Explain how a TM can be viewed as a computing device on functions involving integers. (ii)Design a TM to compute f(m,n)=m*n, for all m,n in Z+. 15. (a) Show that the language Lu is recursively enumerable but not recursive (or) (b) (i) Explain about PCP (ii) Show that Ld is neither recursive nor recursively enumerable
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.