7. Transition table of a Turing machine is given below:
Pres ent
State
Tape Sym bols
Ini tial State→
b
0
1
finite state
→ q 1
1Lq 2
0Rq 1
q 2
bRq 3
0Lq 2
1Lq 2
q 3
bRq 4
bRq 5
q 4
0Rq 5
0Rq 4
1Rq 4
q 5
0Lq 2
Draw the computation sequence of the input string 00.
8. Explain how a Turing-machine can be used as a language acceptor.
9. Prove that not all languages are recursively enumerable.
10. (a) What is Rice’s Theorem?
(b) List six unsolvable problems.
11. (i) Construct a minimal finite automaton for the given FA.
(ii) Below are a number of language over {0, 1}. In each case, decide
whether or not the language is regular, and prove that your answer
is correct.
(a) The set of all strings x beginning with a non null string of the
form WW.
(b) Set of all strings x containing some non null substring of the
form WW.
(c) Set of all strings x containing some non null substring of the
form WWW.
(d) Set of all length strings over {0,1} with middle symbol 0.
University Question Papers
339
1
0
2
3
4
5
6
7
0
1
1
1
1
1
0
0
0
1