Pushdown Automata (PDA) can verify regular language as well as context free language.
There is a known algorithm available to construct PDA from a grammar ( if the grammar is context free ).
PDA has an extra component called a stack. The stack provides additional memory.
PDA can accept languages in 2 ways – acceptance by empty stack and acceptance by final state.
We can construct a deterministic PDA of all regular languages.
Every nondeterministic finite automata can be converted to corresponding deterministic automata but every non-deterministic PDA cannot be converted to a deterministic PDA.
The expressive power of non-deterministic PDA is more than the expressive power of deterministic PDA. It means there exists a context free grammar for which we cannot construct deterministic PDA. For example, we cannot construct deterministic PDA for .
There is no know algorithm to determine if there exists a deterministic PDA for a grammer.
PDA cannot recognize context-sensitive and unrestricted grammar.
It is undecidable if a PDA recognizes , set of all strings over input characters.