Question $5$

Building a Turing Machine

Build a Turing Machine $($TM$)$ that

accepts all words in $\{b^m{a}^n|n>m,m0\},$

loops forever on all words starting with $a,$ and

rejects all other words.

Assume that the alphabet is $L=\{a,b\}$

Hint:

Write out your solution as high level pseudocode before you start drawing your TM$.$ This

will help you to formulate an approach to solving the problem.

For shortest word acceptid $(4$ marks$)$

General words accepted $(6$ marks$)$

For general words which should be rejected $(4)$