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