m0 mL toR rew acc atR back c0 ga gb ⊢ → ⊢, R A → A, R B → B, R a → A, R b → B, R P → P, L Q → Q, L ⊣ → ⊣, S a → a, R b → b, R P → P, L Q → Q, L ⊣ → ⊣, L a → P, L b → Q, L a → a, L b → b, L A → A, R B → B, R P → P, L Q → Q, L A → A, L B → B, L x → x, L y → y, L ⊢ → ⊢, R x → x, R A → x, R B → x, R y → y, S A → A, R B → B, R y → y, R P → y, L A → A, R B → B, R y → y, R Q → y, L
The machine as drawn — 10 states, 38 transitions.
The author’s examples, run ε → accept abab → accept aa → accept aabbaabb → accept a → reject bbab → reject ba → reject babbaabb → reject
Definition $$ \begin{aligned} M &= (Q, \Sigma, \Gamma, \delta, q_0, F) \\Q &= \{ m_{0}, \text{mL}, \text{toR}, \text{rew}, \text{acc}, \text{atR}, \text{back}, c_{0}, \text{ga}, \text{gb} \} \\\Sigma &= \{ \text{a}, \text{b} \} \\\Gamma &= \{ \text{a}, \text{b}, \text{$\vdash$}, \text{A}, \text{B}, \text{P}, \text{Q}, \text{$\dashv$}, \text{x}, \text{y}, \text{$\sqcup$} \} \\q_0 &= m_{0} \\F &= \{ \text{acc} \} \\\delta &: Q \times \Gamma \to Q \times \Gamma \times \{L, R, S\} \\\text{Tape bound} &: |\text{tape}| \le |w| \end{aligned} $$
Verified by the library ✓ Tests pass — 8 examples checked ✓ Deterministic
Machine code lba.ab.ABPQxy:---------------------------lRB_---3RC4RC3RB4RB5LD6LD---------rSZ_---1RC2RC------5LE6LE---------rLE_---------3LD4LD5LD6LD7LD8LDlRF_---5LG6LG------------------_---------7RH7RI------7RF8SZ_---1LG2LG3RB4RB------------_---------3RH4RH8LD------8RH_---------3RI4RI---8LD---8RI
Size 10 states · 38 transitions Level Advanced Licence Creative Commons Attribution 4.0 Tags copy-language context-sensitive finding-the-middle