Q$3$ Semi$-$Thue Systems

$2$ Points

In this problem, consider the Turing machine M with $=\{0,1\},\backslash$Gamma $=\{0,1,\},$ Q $=\{8,$

qaccept, greject$)$ and transitions

R

$0$ R

$0$

R

$1$ qaccept $1$

$8$

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

Suppose that we construct the semi$-$Thue system Thae simulating M$.$

Q$3\mathrm{.}1$ Type $($i$)$ substitutions

$1$ Point

The number of substitutions of type $($i$)$ in Thue is

Q$3\mathrm{.}2$ Derivation

$1$ Point

As M accepts word $01,$ there exists a unique derivation in Te$.$ The number of steps $($that is$,$ substitutions$)$ in this derivation is

$$8018$

$qaccept

Before answering this question, it is recommended that you write the entire derivation. The number of steps is one less than the number of words in the derivation.