s m2 acc c0 c1 g0 g1 ld lr h0 rs h1 adv adv2 adv3 adv4 adv5
The machine as drawn — 17 states, 80 transitions.
The author’s examples, run #0#1 → accept #01#10#11 → accept #0#01#1 → accept #1#1 → reject #0#1#0 → reject ## → reject # → accept #10#10#0 → reject
Definition $$ \begin{aligned} M &= (Q, \Sigma, \Gamma, \delta, q_0, F) \\Q &= \{ \text{s}, m_{2}, \text{acc}, c_{0}, c_{1}, g_{0}, g_{1}, \text{ld}, \text{lr}, h_{0}, \text{rs}, h_{1}, \text{adv}, \text{adv2}, \text{adv3}, \text{adv4}, \text{adv5} \} \\\Sigma &= \{ \text{0}, \text{1}, \text{\#} \} \\\Gamma &= \{ \text{0}, \text{1}, \text{\#}, \text{x}, \text{$\sqcup$}, \text{y}, \text{o}, \text{i} \} \\q_0 &= \text{s} \\F &= \{ \text{acc} \} \\\delta &: Q \times \Gamma \to Q \times \Gamma \times \{L, R, S\} \end{aligned} $$
Verified by the library ✓ Halts — 1 steps ✓ Tests pass — 8 examples checked ✓ Deterministic
Machine code tm.%2301.ioxy@h:0SZ6RB------------------_0SZ7LC2RB3RB------------_---1LC2LC3LC4LC5LC6RD7LC_---1RE5RF4RG4RD5RD---7RH_---1RE2RE3RE4RE5RE---7RH_---1RF2RF3RF4RF5RF---7RI_---1RG2RG3RG4RG5RG---7RJ_------2LK3LK4RH5RH------_0LK1LK5LC3LK4RI5RI------_0LK1LK2LK4LC4RJ5RJ------_0LK1LK2LK3LK3LK2LK6RL7LK_---1RL2RL3RL---------1RM_0LN7LC2RM3RM------------_---1LN2LN3LN------1RO---_---6RP2RO3RO------------_0SZ7LC2RP3RP------------
Size 17 states · 80 transitions Level Advanced Source Sipser, Introduction to the Theory of Computation, §3.1 (M4) Licence Creative Commons Attribution 4.0 Tags textbook sipser element-distinctness zigzag