Question $2$

Given the pscudo$-$code of a Turing Machine M below, answer the following questions. Note that the input alphabet is $\{0,1,2).$

$M="$On input string w:

Put the input on tape and place the tape head on the first symbol of the input.

Repeat the following until no more $0$s left on tape.

a$.$ Replace the leftmost $0$ with $x.$

b$.$ Scan right until a $1$ occurs. If therg are no is$,$ reject.

c$.$ Replace the leftmost I with $x.$

d$.$ Scan right until a $2$ occurs. If there are no $2$ s$,$ reject.

e$.$ Replace the leftmost $2$ with $x.$

f$.$ Return tape head to left$-$hand end of tape, and go to stage $3.$

If all symbols on the tape are blank, reject.

If all symbols on the tape are $x$ or blank, accept; othervise, reject.

Answers:

a$)$ Describe the language that is recognized.

$q,$

b$)$ Find and specify the worst case time complexity of the algorithm. Justify your answer.

Time complexity:

Justifieation:

c$)$ Find and specify the space complexity of the algorithm. Justify your answer.

Space complexity:

Justification: