Pushdown Automaton for Balanced Brackets
Use a stack to recognize nested round and square brackets and locate the first mismatch.
Free theory articleUse a stack to recognize nested round and square brackets and locate the first mismatch.
Concept & interpretation
A deterministic pushdown automaton (DPDA) augments a finite-state control with an unbounded Last-In, First-Out (LIFO) stack, enabling exact recognition of the context-free Dyck language of balanced round and square brackets.
Experiment
Test balanced words, premature closes, and unclosed prefixes in https://riano.app/module/pushdown-automaton:
- Start with default
(())[]and click Step through all 6 characters plus the final EOF step to watch the stack empty and transition from Pending to Accepted. - Enter
([)]and click Finish to verify immediate rejection at 0-based Failure index 2. - Enter
([and click Finish to verify rejection at Failure indexEOFwith 2 unclosed brackets left on the stack.