Deemed University 2009 M.Tech Computer Science & Engineering University: Lingayas University Term: I Title of the : Theory of Computations - Question Paper

Roll No. ..

 

Lingayas University, Faridabad

M.Tech (Term I)

Examination October, 2009

Theory of Computations

Paper: CS -501

[Time: 3 Hours] [Max. Marks: 100]

 

Before answering the question, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.

 

Note: Question No. 1 Part A is compulsory. Attempt any two questions from Part B and any two questions from Part C.
In all attempt five questions.

 

Part A

Q 1.

(i) Construct DFA accepting all strings ending with 00 over the alphabets {0,1}. (2)

(ii) State the conditions for a tree to be a derivation tree. Give example. (2)

(iii) Define push down automata. Give example. (2)

(iv) Construct a PDA equivalent to the following grammar:
S→aAA, A→ aS/bS/a. (2)

(v) State the conditions for equivalence of regular grammar and finite automata. (2)

(vi) State the conditions for valid computation of a Turing machine. (2)

(vii) Define recursive language. Give example. (2)

(viii) State undecidability problem. Give example. (2)

(ix) State posts correspondence theorem. Give its importance. (2)

(x) Define time complexity and give its importance.

 

Part B

Q. 2. (a) Let G = (V, T, P, S) be a context-free grammar, where V and T are finite sets of variables and terminals, respectively, P a finite set of productions, and S the start symbol. Prove that for every A in V, A* if and only if there is a derivation tree in grammar G with yield . (10)

(b)  State and prove pumping lemma for regular sets and prove that the language L over {a}.

L= {| i 1 } is not regular. (10)

Q 3. (a) Explain how Turing machine is used in recognizing a language. Design a TM which accepts the language.

L = {0ⁿ 1ⁿ | n 1} (10)

(b) Describe the concept of Random Access Turing Machine. (5)

(c) Explain what is halting problem in Turing Machines. Illustrate with example. (5)

Q. 4. (a) State and prove Rice theorem for recursive index sets. (10)

(b) Prove the following:-

(i) If a language L is recursive then is also recursive. (5)

(ii) If language L₁ and L₂ are both recursive then

L₁ U L₂ is also recursive. (5)

 

Part - C

Q 5. (a) Convert the following NFA into DFA (10)

 

(b) Convert the following Mealy machine into Moore machine (10)

 

 

Q 6. (a) Convert the following grammar to Chomsky Normal form

S → aAD , A →aB | bAB , B → b , D → d

(10)

(b) Construct PDA equivalent to the following grammar:

S→ aAA, A → aS | bS | a. (5)

(c) Explain the concept of context-sensitive language. Illustrate this with examples. (5)

Q 7. (a) Explain what is multi-headed TM. Show that if language L is accepted by some k headed TM M₁, then it is also accepted by one headed TM M₂. (10)

(b) Describe how to devise binary code for Turing machine? How can this code be used to design universal Turing Machine. (10)

Q 8. (a) Describe how the time and space complexity of a Turing machine is measured with the help of a suitable example. (10)

(b) Find the time and space complexity of Turing Machine which accepts the language. (10)

L = { w w^T | w (a, b)*}