Laboratorium 2020-03-09

$3 \cdot 4$

in : > 1 1 1 # 1 1 1 1 _ _ _ ...
tmp: >
out: >

$$(q_0, S, D) = (q_0, >, >, \_, \_, \_)$$ $$(q_0, S, S_1) = \begin{cases} (q_o, \_, \_, \rightarrow, \_, \_): s \neq \_\\ (q_1, \_, \_, \leftarrow, \_, \_): s = \_ \end{cases}$$ $$(q_1, S, S_1) = \begin{cases} (\widetilde{q_1}, 1, \_, \leftarrow, \rightarrow, \_): s = \_ \\ (halt, \_, \_, \_, \_, \_): s \neq 1 \end{cases}$$

$$(\widetilde{q_1}, S, S_1) = \begin{cases} (\widetilde{q_1}, 1, \_, \leftarrow, \rightarrow, \_): s = 1 \\ (q_m, \_, \_, \leftarrow, \leftarrow, \_): s = \# \end{cases}$$

in : > 1 1 1 # 1 1 1 1 _ _ _ ...
           ^
tmp: > 1 _ 1 1 _
             ^
out: > _
       ^

$(q_m, 1, 1) = (q_m, 1, 1, \_, \leftarrow, \rightarrow)$