17

18

19

20

b)
a)
b)
a)
b)

a)
b)

E192010 Pages:3

simulate the moves of a Turing Machine

Write a note on Universal Turing machines.

How to identify deterministic Turing machine from nondeterministic TM

Write notes on the following:

i) decidable and undecidable problems

ii) Halting Problem of Turing machine.

Write the properties of recursive languages and recursively enumerable
languages.

Write the Chomsky hierarchy of languages. Prepare a table indicating the
automata and grammars for the languages in the Chomsky Hierarchy.

Define Turing machine [Write the tuple representation for TM].

Design a Turing machine to identify the strings belong to the language L={0"1"
| n>O}.

Design the Turing machine to recognize the language: {0"1"0" |n >=1}.

Page 3 of 3

Ww

10