How to design DPDA and NPDA:


PDA Design method:


Process to design a DPDA and NPDA is similar. For DPDA as we know for every single input only one move is possible because it is deterministic.


Design DPDA:


Let consider two transition functions 



Design NPDA :


Because of it is non-deterministic for one input more than one move is possible.


Let consider the two transition function:




Now the corresponding NPDA:



Machine accepts string if it reaches final state F. machine reject string if it never reaches final state F or dead the machine in any state.


Here we describe some of the operation possible for PDA:


  • We can push a finite string at a time:


  • But pop one symbol from TOS:


  • TOS unchanged:


  • Rewrite the TOS:


Now if owe consider a PDA which consists only move like third one above i.e.



It means stack is unchanged after operation. In that case we can treated PDA as DFA/NFA because we can rewrite,



So, for this type of PDA, it can easily convert to Finite Automata (FA).


Now, we can say any work perform be DFA/NFA, which also can be done by PDA.


How Push Down Automata accept the string


M: DPDA and NPDA accept string in two ways.


String acceptance by final state.


 String acceptance by empty stack.


Using any of the method we use to design a PDA. Or we convert 1 to 2 or 2 to 1 both are equivalent.


There should be an algorithm where machine produce by 1 is converted a machine produce by 2.


It is also possible that we design a machine where both 1 and 2 are present at a time.


 both final state and  empty stack.