THEORY OF COMPUTATION 2005 NOV DEC Question PAPER

 Maximum: 100 marks

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2005.
 Fifth Semester Computer Science and Engineering
CS 332 - THEORY OF COMPUTATION
Time: Three hours
 Answer ALL questions.

PART A - (10 x 2 = 20 marks)

1. Obtain (E -closure of each state in the following NFA with E -move.
2. Define regular expression and give an example.
 3. For the grammar S -> aCa , C -> aCa lb, find L(G).
4. Show that id + id * id can be generated by two distinct leftmost derivation in the grammar E -> E + E IE * E I(E)lid.
5. Give an example of a PDA.
6. Explain the acceptance of a PDA with empty stack.
7. Describe the non-deterministic Turing machine model. Is it true the nondeterministic Turing machine model's are more powerful than the Basic Turing machines? (In the sense of language acceptance).
 8. When a language is said to be recursive? Is it true that every regular set is not recursive?
9. When a problem is said to be decidable or undecidable? Give an example of an undecidable.
10. What do you mean by Universal Turing machine? softwaretrojans.blogspot.com



PART B - (5 x 16 = 80 marks)

11. (i) Design Turing machine for computing f(m,n)=m-n (proper subtraction). (10) (ii) Explain how the multiple tracks in a Turing machine can be used for testing given positive integer is a prime or not. (6)

 (ii) Check whether the language L = {on ln /n > 1} is regular or not? Justify your answer. (6) Or (b)(i) Construct an NFA equivalent to the regular expression ((0 + 1)(0 + 1)(0 + 1))*. (8) (ii) Obtain the regular expression denoting the language accepted by the following DFA by using the formula Rij (8)

13. (a) (i) Let G = (V,T,P,S) be a context-free grammar. Then prove that if S =*:>a then there is a derivation tree in G with yield a. (10) (ii) Find a context free grammar with no useless symbols equivalent to S -> AB/CA , B -> BC/AB A ->a, C -> aB/b. (6) Or
(b) (i) Obtain the Chomsky normal form equivalent to the grammar S -> bA/aB, A -> bAA/aS/a, B --> aBB/bS/b. (4) (ii) Convert the grammar S-->AB, A-->BS/b, B->SA/a into Greibach normal form. (12)

14. (a) (i) Prove that L is L(M2) for some PDA M2 if and only if L is N(Mj) for same PDA M,. (12) (ii) Define deterministic push down automata DPDA. Is it true that DPDA and PDA are equivalent in the sense of language acceptance is concern? Justify your answer. (4) Or (b) (i) Construct a context-free grammar G which accepts N(A) where (10) (ii) State pumping lemma for context-free language a show that language (aibjcidj / i ≥1, and j ≥ 1) is not context-free. (6)

15. (a) Define the language Lu Check whether Lu , is recursively enumerable? or Lu is recursive? Justify your answers. (16) Or (b) (i) Show that the language Ld is neither recursive nor recursively enumerable. (12) (ii) Describe how a Turing machine can be encoded with 0 and 1 and give an example. (4)

Click To Download