mdu question paper for CSE (TCA) 4th sem

B.tech 4th sem (CSE) Examination, May -2009
THEORY OF COMPUTATION AND AUTOMATA
PAPER-CSE-206-E

1(a) Let X be a sting in {0,1}* of length n. Describe an FA that accept the string X and so other strings. How many state are required ? 10

(b)Suppose M=(Q,∑,qₒ,A,δ) is an FA and suppose that there is some string Z so that for every qєQ, δ*(q,Z)єA. What conclusion can you derive and why? 10


2 If M₁ = (Q, ∑, Δ, δ, qₒ) is a Mealy machine .Prove that there is a Moore machine M₂ equivalent to M₁. convert the following Mealy m/c to Moore m/c :



3. Using the concept of pumping lemma prove that following language are not regular

(a) aⁿbᵐ I n>m

(b) aᶤ bᶨ I 1<=i<=Z and j >=i

(c) aᶤ bᶨ cᵏ dᶥ I I + k = j + l 20




4 (a) Obtain an equivalent right linear grammar for the following left linear grammar

S -> Abc / c

A -> Acc / bc


(b)For the following grammar find an equivalent grammar with no useless symbols.

A -> xyz / Xyzz

X -> Xz / xYx

Y -> yYy / XZ

Z -> Zy / z 20


5 (a) Construct a PDA accepting
L = { aᶤ bᶨ /j = i or j = 2i } 10

(b) What are the main application of PDA ? Discuss briefly. 10


6. Design a turing machine which can find out the remainder when the first number (M) is divided by second number (N). 20


7. (a) Give unrestricted grammars for :

(i) { ww / w is in ( 0 + 1)*}
(ii) {0ᶤ / i is not prime}
(iii) {0ᶤ 1ᶤ 2ᶤ / i>=1} 15

(b) show that the CSL are closed under intersection. 5


8. (a) What is a primitive recursive function ? Show that
f(x, y) = x * y is primitive recursive.

(b) Show that Fibonacci numbers are generated by a primitive recursive function. 20