Q$7(5$ points$)$

Given the below non deterministic Turing Machine:

a$)$ Show the computation tree of the string aca $.(1\mathrm{.}5$ marks$)$

b$)$ Show the first $8$ steps only of the simulation showing the values on the three tapes

of the multi$-$tape deterministic Turing machine equivalent to the above

nondeterministic Turing Machine. Show where is the location of the head on each

tape at each time. Address the nodes in the computation from point a of this question,

address the root node as well. $(2\mathrm{.}5$ marks$)$

c$)$ Show the single tape representation for the last step in point b of this question $(1$

mark$)$