Advantages and Disadvantages of Pushdown Automata

Advantages

1. Pushdown Automata (PDA) can verify regular language as well as context free language.
2. There is a known algorithm available to construct PDA from a grammar ( if the grammar is context free ).
3. PDA has an extra component called a stack. The stack provides additional memory.
4. PDA can accept languages in 2 ways – acceptance by empty stack and acceptance by final state.
5. We can construct a deterministic PDA of all regular languages.

Disadvantages

1. Every nondeterministic finite automata can be converted to corresponding deterministic automata but every non-deterministic PDA cannot be converted to a deterministic PDA.
2. 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 .
3. There is no know algorithm to determine if there exists a deterministic PDA for a grammer.
4. PDA cannot recognize context-sensitive and unrestricted grammar.
5. It is undecidable if a PDA recognizes , set of all strings over input characters.