Pushdown Automaton for Balanced Brackets

Why Finite Automata Cannot Count Arbitrary Nesting

By the pumping lemma for regular languages, a finite automaton with a fixed number of states cannot remember an arbitrarily deep sequence of open brackets ( and [ in the exact reverse order required to match closing brackets ) and ]. Pushing each opening delimiter onto a LIFO stack and popping on its matching closer resolves nested dependencies in linear time.

Deterministic Transition and Acceptance Rules

For an input word w over the alphabet {(, ), [, ]}, the automaton starts with an empty stack. At each 0-based index i: if w[i] is ( or [, push w[i] onto the stack; if w[i] is ) (or ]), require the stack top to be ( (or [) and pop it, otherwise halt and reject immediately with failure index i. If all characters are consumed without mismatch, the word is accepted at EOF if and only if the remaining stack is empty; otherwise it is rejected with failure index EOF.

Worked Example

Compare an accepted nested string [()[]] with a mismatched string ([)]:

1. Index 0 of ([)]: Read ( and push onto the stack. Stack is ["("].
2. Index 1 of ([)]: Read [ and push onto the stack. Stack is ["(", "["].
3. Index 2 of ([)]: Read ). The top of the stack is [ rather than (. The automaton halts and rejects immediately at 0-based Failure index 2 with remaining stack ["(", "["].
4. Contrast with [()[]]: Every closing bracket matches the top of the stack and EOF is reached with stack length 0, so Accepted = true and Failure index = None.

Experiment

Test balanced words, premature closes, and unclosed prefixes in https://riano.app/module/pushdown-automaton:

1. 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.
2. Enter ([)] and click Finish to verify immediate rejection at 0-based Failure index 2.
3. Enter ([ and click Finish to verify rejection at Failure index EOF with 2 unclosed brackets left on the stack.

Limitations

The interactive UI bounds input length to 0..12 characters over two bracket types so every tape cell and stack frame fits clearly on screen. While any finite-length language is technically finite, the pushdown transition rules demonstrated here generalize to arbitrary unbounded lengths without adding states.

Common Pitfalls

Simply counting whether the number of ( equals ) and [ equals ] is insufficient: cross-nested strings like ([)] have equal counts of each bracket type yet violate LIFO nesting order.

References

Formal definitions and visual traces of pushdown automata for balanced parentheses follow standard automata theory references:

• JFLAP Tutorial: Constructing a Pushdown Automaton