$(40$ Points$)$ Given the following language, $L_2=\{\begin{array}{c}x\\ \text{y}\text{i}\text{n}& \{0,& 1{\}}^{**}\end{array}$ and $\{$:$xy\},$

$($a$)(6$ Points$)$ List $3$ pairs of strings are in $L_2.$

$[$ANSWER$]$

$($b$)(4$ Points$)$ List $2$ pairs of strings are NOT in $L_2.$

$[$ANSWER$]$

$($c$)(30$ Points$)($i$)(10$ Points$)$ Write down the pseudo code algorithm in English

for a Turing machine $($TM$)$ that recognizes $L_2.$ Assuming input string on the

tape is $x$ concatenated with a letter $w$ followed by $y.$ For instance, if $x=$

$"1010"$ and $y="1100"$ then the input string on the tape will be $"1010$w$1100$

$-".($ii$)(20$ Points$)$ Construct the graphical Turing Machine $($TM$)$ for

recognizing $L_2.$ Please note that no transition tables needed.

$[$ANSWER$]$