Tamil University Model question paper - 2009 model question papers

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

Course: B.E Computer Science and Engineering   University/board: Tamil University

SUBJECT : Theory of Computation SUBJECT CODE: CS1303
TIME : 3Hrs Total Marks :100

PART A (10*2=20)
1. What is the difference between NFA and DFA?
2. Define e-closure 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.

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}

(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?
(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 context-free 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.
(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.
(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
(b) (i) Explain about PCP
(ii) Show that Ld is neither recursive nor recursively enumerable

Return to question paper search

Next Question Paper: Final professional exam Surgery Paper 1 2008 (resit batch) May

Previous Question Paper: Model question paper 3rd semester, electrical & electronics engineering

Related Question Papers:

  • T.Y.B.Com Examination, March 2009 - Economics (Revised Course) University Question

  • T.Y.B.Com Examination, March 2009 - Economics (OLD Course) University Questions

  • T.Y.B.Com Examination, March 2009 - M.P.P University Question paper

  • T.Y.B.Com Examination, March 2009 - Economics (OLD Course) University Question paper

  • Title of the paper: PROGRAMMING IN C

  • Categories

    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.

    Looking for University or College admissions in India for 2021 - 2022 Academic Year?

    Top Contributors
      Last 7 Daysmore...

      Awards & Gifts

      Online Members

      SpiderWorks Technologies Pvt Ltd, Kochi - India. © All Rights Reserved.