> For example, a BNF grammar can be described by a state machine whose states are sequences of terminals and/or non-terminals.
Eh... for BNF grammars, you'd need a stack. Or an infinite state machine.
Eh... for BNF grammars, you'd need a stack. Or an infinite state machine.
"For example, a BNF grammar can be described by a state machine whose states are sequences of terminals and/or non-terminals. The set of initial states contains only the sequence consisting of the single starting non-terminal. The next-state relation is defined to contain <s, t> iff s can be transformed to t by applying a production rule to expand a single non-terminal."
I suppose you could represent a PDA as an infinite state machine but the "stack" abstraction is kept around because it's clearer/easier to reason about. See, for example, the proof that CFLs are accepted by NPDAs and its correspondence with LR0 parsing.