FOR FREE MATERIALS

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.

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.