3 ms·
Isn't a stack just a "sequence of terminals and/or non-terminals"? (Or as you suggested, an infinite state machine where the states are all possible sequences o
by obastani 11y ago
Isn't a stack just a "sequence of terminals and/or non-terminals"? (Or as you suggested, an infinite state machine where the states are all possible sequences of terminals and/or non-terminals.)
- superuser2 11y agoA pushdown automaton's stack alphabet is arbitrary (so you could make it "terminals union nonterminals" but you don't have to) and finite (so you could not make it "all sequences" without a length cap). 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.