Library

MTM · Recursively enumerable

Balanced parentheses, with a second tape for a stack

A Turing machine has no stack, but a second tape is one: write a mark and step right for each (, step left and erase for each ). One pass, against the one-tape machine’s walking back and forth to find each partner.

q0runpoppoppedendacc
The machine as drawn — 6 states, 7 transitions.

The author’s examples, run

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