Pushdown automaton (PDA)
Pushdown automaton is an extension of an NFA One thing added to PDA is an input window, a read-only string in memory, where each character is read once, no backtracking is allowed. Another is a stack, read-write memory implemented as stack, with all its properties. Note that a non-deterministic PDA is stronger than a deterministic PDA (with no proof), which is why we define PDA to be non-deterministic.
PDA definition
Configuration definition
Configuration is a “snapshot” of the current state of PDA.
Step-relation definition
PDA language definition
Example
Example
Equivalence of CFG and PDA theorem
Closure under intersection lemma
Regular grammars
Regular grammars can be right or left.
A left regular grammar differs only in the position of