B.Tech IV (Fourth) Semester Examination 2012-13

Course Code:ECS401 Paper ID:0964108

Theory of Computation

Time: 3 Hours Max. Marks: 70 Max Marks: 75

Note: Attempt six questions in all. Q. No. 1 is compulsory.

1. Answer any five of the following (limit your answer to 50 words). (4x5=20)

a) Describe transition system.

b) Define regular expression with example.

c) Define useless and useful symbols. Give example.

d) Differentiate between GNF and CNF.

e) State the pumping lemma for CFL.

f) Define push down Autometa with an example.

g) Define ID and move of a Turing Machine.

h) Differentiate recursive and recursively enumerable language.

2.a) Convert the following NDFA into its equivalent DFA: (5)

State / Input
0 / 1
q0 / q0, q1 / q1
q1 / q2 / q2, q0
q2 / - / q2

b) Prove that for each NFA which accept a language L. There exist an DFA which also accept L. (5)

3. Explain pumping lemma for regular sets. Using the concept of PL. Prove that

is not regular

is not regular. (10)

4. a) Construct a minimum state automaton equivalent to a given automaton M where transition table is given below: (5)

State / Input
a / B
q0 / q0 / q3
q1 / q2 / q5
q2 / q3 / q4
q3 / q0 / q5
q4 / q0 / q6
q5 / q1 / q4
q6 / q1 / q3

b) Explain Mealy and Moove Machine with example. (5)

5. Show that recursively enumerable languages are closed order intersection. (10)

6. a) Construct push down autometa for the following language.

(5)

b) Let G be the grammar (5)

7. Explain Chomsky Normal Form and Greiback Normal Form. Convert the following grammar into Chomsky Normal Form.

(10)

8. Design Turing Machines to recognize the string with an equal number of O’s and 1’s. (12)