Library

DPDA · Deterministic context-free

Unbalanced parentheses

Deterministic context-free languages are closed under complement — unlike context-free languages in general — and this is what that looks like. Run the bracket checker; if a ) ever finds nothing to match, or the input ends with a ( still open, accept instead of reject.

evenopenbrokencheck
The machine as drawn — 4 states, 8 transitions.

The author’s examples, run

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