(e) Set of non palindromes.
(f) Set of strings in which the number of 0’s and the number of
1’s are both divisible by 5.
12. What is a non deterministic turing machine? Explain how is it used for
computing.
13. (a) (i) Construct a turing machine that can accept the strings over
{0, 1} containing even number of 1’s.
(ii) Construct a turing macine that can accept the set of all even
palindromens over {0, 1}.
(OR)
(b) M is a turing machine represented by the transition system as in
the figure given. Obtain the computation sequence of M for
processing the i/p string 0011.
340
Theory of Automata, Formal Languages and Computation
q 2
q 4
q 1
q 3
q 5
q
(1,,) xR
(0) ,x,R
(1) ,y,L
() x,x,R
() b,b,R
() y,y,R
() y,y,L
() b,b,R
(00) ,,L
(00) ,,L