Library

DFA · Regular

Parentheses nested at most three deep

Balanced parentheses need a stack in general. With the depth capped at three, the depth itself is the state: a bounded counter is a finite automaton.

d0d1d2d3((()))
The machine as drawn — 4 states, 6 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

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