Hacker News new | past | comments | ask | show | jobs | submit login

A 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.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: