Library

LBA · Context-sensitive

A word repeated twice: ww

Without a separator the machine must find the middle itself: it capitalises letters alternately from the left and from the right until the two ends meet. Then it compares the halves letter by letter. An odd-length word is caught when the ends cross.

m0mLtoRrewaccatRbackc0gagb⊢ → ⊢, RA → A, RB → B, Ra → A, Rb → B, RP → P, LQ → Q, L⊣ → ⊣, Sa → a, Rb → b, RP → P, LQ → Q, L⊣ → ⊣, La → P, Lb → Q, La → a, Lb → b, LA → A, RB → B, RP → P, LQ → Q, LA → A, LB → B, Lx → x, Ly → y, L⊢ → ⊢, Rx → x, RA → x, RB → x, Ry → y, SA → A, RB → B, Ry → y, RP → y, LA → A, RB → B, Ry → y, RQ → y, L
The machine as drawn — 10 states, 38 transitions.

The author’s examples, run

ε → acceptabab → acceptaa → acceptaabbaabb → accepta → rejectbbab → rejectba → rejectbabbaabb → reject