$1.$ Consider the Turing machine, M$,$ shown below.

$($Grafstate code for this machine is at the end of the $.$tex document$)$

$($a$)7$ points Show the computation of the string abac in this machine.

Note, abac epsilon in L$($M$).$

q$\_0$abac $|-$$q$\_1$bac

$|-$

b$)8$ points Show the computation of the string accba in M$.$ Note,

accba exculed from L$($M$).$

q$\_0$accba $|-$$q$\_1$ccba

$|-$

$($c$)8$ points What is L$($M$)?$

Fig $1$ grafstate code

:$+$ tm TM$1$

title Problem $1$

Q$=\{$q$0,$q$1,$q$2,$q$3,$q$4,$q$5,$q$6,$q$7,$qa$,$qr$\}$;

S$=\{$a$,$b$,$c$\}$;

T$=\{$a$,$b$,$c$,\backslash \_,$X$,$$$\}$;

q$0=$q$0$;

q$0->$q$1$: a$->$$$,$R;

q$0->$qr: b$->$b$,$R;

q$0->$qr: c$->$c$,$R;

q$0->$qr: $\backslash \_->\backslash \_,$R;

q$1->$q$1$: X$->$X$,$R;

q$1->$q$2$: b$->$b$,$R;

q$1->$q$2$: c$->$c$,$R;

q$1->$q$3$: a$->$X$,$L;

q$1->$qa: $\backslash \_->\backslash \_,$L;

q$2->$q$2$: b$->$b$,$R;

q$2->$q$2$: c$->$c$,$R;

q$2->$q$2$: X$->$X$,$R;

q$2->$q$3$: a$->$X$,$L;

q$2->$qr: $\backslash \_->\backslash \_,$L;

q$3->$q$3$: b$->$b$,$L;

q$3->$q$3$: c$->$c$,$L;

q$3->$q$3$: X$->$X$,$L;

q$3->$q$4$: $$->$$$,$R;

q$4->$q$4$: a$->$a$,$R;

q$4->$q$4$: c$->$c$,$R;

q$4->$q$4$: X$->$X$,$R;

q$4->$q$5$: b$->$X$,$L;

q$4->$qr: $\backslash \_->\backslash \_,$L;

q$5->$q$5$: a$->$a$,$L;

q$5->$q$5$: c$->$c$,$L;

q$5->$q$5$: X$->$X$,$L;

q$5->$q$6$: $$->$$$,$R;

q$6->$q$6$: a$->$a$,$R;

q$6->$q$6$: b$->$b$,$R;

q$6->$q$6$: X$->$X$,$R;

q$6->$q$7$: c$->$X$,$L;

q$6->$qr: $\backslash \_->\backslash \_,$L;

q$7->$q$7$: a$->$a$,$L;

q$7->$q$7$: b$->$b$,$L;

q$7->$q$7$: X$->$X$,$L;

q$7->$q$1$: $$->$$$,$R;

done.