0 0 votes Consider $L=\{0^n1^n2^n\mid n\ge0\}.$Which of the following gives a correct high-level strategy for a single-tape Turing machine recognizing $L$?Repeatedly mark the leftmost unmarked $0$, then the leftmost unmarked $1$, then the leftmost unmarked $2$; return to the left end and repeat. When no unmarked $0$ remains, accept only if no unmarked $1$ or $2$ remains. Mark all $0$'s first, then all $1$'s, and finally all $2$'s. Accept whenever all symbols have been marked. Compare the first $0$ only with the final $2$. If they exist, accept without checking the number of $1$'s. Scan the input once from left to right using only the finite control to remember the exact number of $0$'s, $1$'s and $2$'s. Theory of Computation goclasses goclasses-cs-dpp theory-of-computation goclasses-cs-dpp-day-381 goclasses-toc-practice-questions turing-machine + – GO Classes 47 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
0 0 votes The machine must enforce $\#0=\#1=\#2$while also ensuring that the input has the form $0^*1^*2^*.$A correct marking algorithm is:Find the leftmost unmarked $0$ and mark it. Move right and find the leftmost unmarked $1$. Mark it. Continue right and find the leftmost unmarked $2$. Mark it. Return left. Repeat. When no unmarked $0$ remains, check that no unmarked $1$ or $2$ remains.If a required matching symbol is missing at any stage, reject.Thus each iteration matches exactly one $0, 1, 2.$ Hence,Answer : A GO Classes answered 3 days ago GO Classes comment Share Follow 0 reply Please log in or register to add a comment.
