Theory of Computation · topic
PDA as a 7-tuple with instantaneous descriptions, acceptance by final state and by empty stack, PDAs for standard languages, NPDA versus DPDA, deterministic context-free languages and the prefix property, and the CFG to PDA and PDA to CFG constructions.
A pushdown automaton (PDA) is an NFA equipped with a stack. The stack provides unbounded memory that is accessible only at the top, which is exactly the power needed for context-free languages: every CFG has an equivalent PDA and every PDA has an equivalent CFG.
A deterministic pushdown automaton (DPDA) never has a choice of move: at most one transition applies for the current state, input symbol (or ε), and top-of-stack symbol, and ε-input moves cannot compete with a defined symbol move. Languages of DPDAs are deterministic context-free languages (DCFLs).
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
