Question $1-$Turing Machines

We let $=\{0,1,$#$\}$ denote an alphabet with three letters. Consider the following Turing Machine $T$ :

The reject state is implicit in the above state diagram: If there is no instruction for a letter in any given state, then the Turing machine will go to the reject state $q_{\text{r}\text{e}\text{j}}.$

Part $1$ Select all configurations that $T$ will go through on input #$00$#$11$#:

$($a$)q_0$#$00$#$11$#

$($b$)$ #$0$q $10$#$11$#

$($c$)x00$#$q_{4}11$#

$($d$)$ xyy# $q_{9}zz$#

$($e$)$ #$y0$#$z{q}_{7}1$#

$5$ points

$2$

$2/4$

Part $2$ Select all configurations that $T$ will go through on input #$0$#$11$#:

$($a$)q_0$#$00$#$1$#

$($b$)x{q}_{5}0$#$11$#

$($c$)xy$#$q_{7}11$#

$($d$)xy$#$zz{q}_5$#

$($e$)$ #$y$#$zz$#$q_{\text{a}\text{c}\text{c}}$

$5$ points

Part $3$ Select all words that are members of $L(T),$ that is all words that are accepted by the Turing Machine $T.$

$($a$)$ #$00$#$1$#

$($b$)$ #$00$#$11$#

$($c$)$ ##

$($d$)$ #$000111$#

$($e$)$ #$0$#$0$#

$($f$)$ #$0000$#$1111$#

$($g$)$ #$0$#$1$

$($h$)$ #$0$#$1$#$0$#

$($i$)$ #$000$#

$($j$)$ #$0$#$1$#

$10$ points

Part $4$ Select all items that are correct statements about $T$ :

$($a$)$ The language $L(T)$ is regular.

$($b$)$ The language $L(T)$ is context$-$free.

$($c$)$ The language $L(T)$ does not contain any palindromes.

$($d$)$ The language $L(T)$ us a subset of $L($#$0^{+}$#$1^{+}$#$).$

$($e$)$ Every subset of $L(T)$ that is a regular language is finite. solve and explain each step