Advantages and Disadvantages of Pushdown Automata


  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.


  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 L = \{ w | w\; is\; palindrome  \}.
  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 \sum*, set of all strings over input characters.

Leave a Comment

Your email address will not be published. Required fields are marked *