$[10$ Points$]$ Simulating a TM with a Semi$-$Thue System. In this problem, consider the Turing machine M with $\backslash$Sigma $=\{0,1\},\backslash$Gamma $=\{0,1,\},$ Q $=\{$s$,$ qaccept, qreject$\}$ and transitions

s $$ s $$ L

s $0$ s $0$ R

s $1$ qaccept $1$ S

Clearly, L$($M$)=\{$w in $\backslash$Sigma $*|$ w contains a $1\}$

Suppose that we construct the semi$-$Thue system T$\_$hue simulating M$.$

$($a$)$ List all of T$\_$hue's substitutions of type $($i$)$

$($b$)$ List all of T$\_$hue's substitutions of type $($ii$)$

$($c$)$ List all of T$\_$hue's substitutions of type $($iii$)$

$($d$)$ As $001$ in L$($M$),$ there must exist a derivation $s$001$$ $$ $qaccept$

Write this derivation.