a)
b)

௦)
a)

b)
a)
b)
0)

000001T303121901

PART (^

Answer any two full questions, each carries 20 marks.
Explain Linear Bounded Automata with an Example.
Design a Turing machine that adds two numbers m and n stored as 1071071 in
the input tape.
State and prove the equivalence of single tape and multi-tape Turing Machine.
List and explain the variants of Turing Machine, and show that they are
equivalent to a single tape Turing Machine.
Prove that Universal Language is recursively enumerable.
Explain Halting problem with an example.
Write a short note on Recursive and recursively enumerable languages.

Distinguish between decidable and undecidable problems.

Page 2 of 2

(4)
(8)

(8)
(12)

(8)
(5)
(9)
(6)