Problem $2$

a$.$ Create a Turing Machine $M$ in JFLAP that accepts

$L=\{\begin{array}{ccc}\text{w}\text{i}\text{n}& \{a,& b{\}}^{+}\text{:}|w|4\\ w\end{array}$ has exactly one $b$ and

it occurs in the last $4$ characters of $w\}$

$[$Hint: See Example $1$ in Chap$9\mathrm{.}1$ Part$2$ Power Point slides.$]$

b$.$ Use JFLAP to test $M$ with input strings:

aabaa, aaaaba $,$ aaaab, aabaaa, aab, baaa, abaaaa $,$ abaab, bbbb

c$.$ Give an instantaneous description trace of $M$ with input $w=$aaaba that

shows that winL$(M).$ Do not use JFLAP to create the instantaneous

description trace of $M.$Example $1$: Do an ID trace on the TM that accepts

: Last $4$ chars of $w$ are abbb, with input

$w=$babbb

$($babb $,$q$0,$ b$)|-($babbb $,$q$0,$ #$)|-($ babb $,$ql$,$ be$)|-($bab$,$ q$2,$

$($ba $,$q$3,$ babb$)$ halt and accept