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.
The author’s examples, run
ε → accept(()) → accept(()()) → accept(()())(()()) → accept( → reject)()) → reject)()()) → reject)()())(()()) → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.