f0 f1 f2 f3 rw round findB tail acc findC ret ⊢ → ⊢, R a → a, R b → b, R c → c, R ⊣ → ⊣, L b → b, R c → c, R ⊣ → ⊣, L c → c, R ⊣ → ⊣, L a → a, L b → b, L c → c, L ⊢ → ⊢, R x → x, R a → x, R y → y, R ⊣ → ⊣, S a → a, R y → y, R b → y, R b → b, R z → z, R c → z, L a → a, L b → b, L c → c, L x → x, L y → y, L z → z, L ⊢ → ⊢, R y → y, R z → z, R ⊣ → ⊣, S
The machine as drawn — 11 states, 34 transitions.
The author’s examples, run ε → accept abc → accept aabbcc → accept aaaabbbbcccc → accept a → reject bbc → reject babbcc → reject baaabbbbcccc → reject
Definition $$ \begin{aligned} M &= (Q, \Sigma, \Gamma, \delta, q_0, F) \\Q &= \{ f_{0}, f_{1}, f_{2}, f_{3}, \text{rw}, \text{round}, \text{findB}, \text{tail}, \text{acc}, \text{findC}, \text{ret} \} \\\Sigma &= \{ \text{a}, \text{b}, \text{c} \} \\\Gamma &= \{ \text{a}, \text{b}, \text{c}, \text{$\vdash$}, \text{$\dashv$}, \text{x}, \text{y}, \text{z}, \text{$\sqcup$} \} \\q_0 &= f_{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.abc.xyz:---------------------lRB_---1RB2RC3RD------------rLE_------2RC3RD------------rLE_---------3RD------------rLE_---1LE2LE3LE---------lRF_---4RG------4RF5RH------rSZ_---1RG5RI------5RG---_---------------5RH6RH---rSZ_------2RI6LJ------6RI_---1LJ2LJ3LJ4LJ5LJ6LJlRF
Size 11 states · 34 transitions Level Intro Licence Creative Commons Attribution 4.0 Tags context-sensitive crossing-off canonical