$16(5$ marks$)$

Consider the following high$-$level description of a Turing Machine. What language on $\{a,b\}$ does

the TM accept?

Sweep Left to Right.

If there is an a after the first b

REJECT

Move head to Start. Search for a$.$

IF found, replace with $x$

ELSE Go to Step $5$

REPEAT twice :

Search for b$.$

IF found, replace with $x$

ELSE REJECT

Go to Step $2.$

Move head to Start. Search for b$.$

IF found, ACCEPT

ELSE REJECT

You may assume that the tape contains only $a$ s and $bs$ at the start.