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