SKR Engineering College 2007 B.E Computer Science Theory of Computation_ - Question Paper

SKR ENGINEERING COLLEGE
DEPARTMENT OF COMPUTER SCIENCE
MODEL ques. 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 ranging from NFA and DFA?
2. describe 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 actual that deterministic push down automata and non deterministic push down automata are equivalent in the sense of language of acceptances?
6. describe instantaneous description of a PDA
7. describe basic Turing machine.
8. discuss multitape Turing machine model
9. When a issue is stated to be un decidable? provide an example of an undecidable issue.
10. Show that the union of recursive language is recursive.

PART-B-(5*16=80)
11. (a) (i) Prove that language L is accepted by a few NFA if and only if L is accepted by a few DFA . (8)
(ii) Consider the subsequent ?-NFA .Compute the closure of every state and obtain 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 a few DFA iff L is accepted by a few NFA.
(ii) Convert the subsequent 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 subsequent 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 provided beneath


0 1
àp {p,q} {p}
q {r} ?
*r ? ?


(ii) Prove that if L=L(A) for a few 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) discuss various kinds of acceptance of a PDA .Are they equivalent in sense of language acceptance? Justify your ans.
(or)
(b) If L is N(M) for a few PDA M ,then prove that L is situation free language

14. (a) (i) Design a TM to accept the language L= { anbn /n?Z+}

(ii) discuss with an example how finite control of a TM can be used to hold a finite amount of info.
(Or)
(b) (i) discuss how a TM can be viewed as a computing device on functions involving integers.
(ii)Design a TM to calculate 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) discuss about PCP
(ii) Show that Ld is neither recursive nor recursively enumerable

Earning:   Approval pending.