Library

TM · Recursively enumerable

Balanced parentheses without a stack

Find the first ), cross it off, walk left to the nearest ( that is still open and cross that off too. When no ) is left, there must be no ( either. The leftmost ( is marked A at the start so the machine can tell when its walk left has run out of room.

startscanaccopencheck( → A, R⊔ → ⊔, S( → (, RX → X, R) → X, L⊔ → ⊔, LX → X, L( → X, RA → B, RX → X, LB → B, S
The machine as drawn — 5 states, 11 transitions.

The author’s examples, run

ε → accept(()) → accept(()()) → accept(()())(()()) → accept( → reject)()) → reject)()()) → reject)()())(()()) → reject

Behaviour

The first steps from a blank tape: one row per step, time running down; the outlined cell is the head.

Halts from a blank tape after 1 steps, leaving 0 non-blank cells.