It is a computational model that can be used to recognize context-free languages that are not context-sensitive. It is a state machine and has the memory of one infinite stack. It is used in the Theory of Computation and for designing compilers.

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

    Log in or register to write something here or to contact authors.