Pushdown Automata (PDA)
Push Down Automata (
PDA's) are
state machines that accept a
language. A PDA is said to
accept a Language (L)
if and only if (L) is
Context Free.
A PDA is similar to a
Deterministic Finite Automata with the exception that the PDA carries a
stack. When
parsing a given
char in an
input string, the PDA not only has the option of switching
states, but also has the ability to
push or
pop a char from the
stack. This stack makes the PDA more powerful than the DFA.
Without a stack the DFA is only able to accept languages if and only if they are
Regular.
A PDA is a language
accepter. A
Context Free Grammar is a language
generator that generates the same class of languages accepted by PDA's.