FOR FREE MATERIALS

DPDA and NPDA:

 

Definition of DPDA:

 

M = {Q, ∑, Г, δ, q0, z, F}

 

All the tuples are already define at previous chapter PDA: Introduction

 

 

We only define here transition function:

 

δ: Q X ( ∑ ⋃ { λ } ) X Г at most one  Q X Г*.     

 

 

 

 

δ: Q X ( ∑ ⋃ { λ } ) X Г at most one Q X Г*  means we can have possibility of zero move or one move because it is deterministic i.e. it is define as at most one  Q X Г*.

 

And we know dead configuration is allowed in both DPDA and NPDA.

 

 

It means λ moves or input is allowed but for λ there should be a choice for DPDA.

 

 

 

Here at DPDA for q0 two choices occurred which is never possible so, if λ is there then, it should not be other choices for any alphabet ∊ ∑. 

 

 

DPDA has only one move possible.

 

Example:

 

 

 

Definition of NPDA:

 

M = {Q, ∑, Г, δ, q0, z, F}

 

All the tuples are already define at previous chapter PDA: Introduction

 

We only define here transition function:

 

δ: Q X ( ∑ ⋃ { λ } ) X Г -- finite subset of Q X Г*, Г – top of stack symbol

z ∊ Г, F ⊆ Q.

 

Means Q X Г* is basically a infinite set [Г* = infinite] like Q  (q0, q1) and Г∊ (a, b) then Q X Г* is,

 

 

But we always take finite subset of this super set Q X Г*.

 

Example:

 

 

So, first it read a and replace top of stack b by cd and one thing string go to stack at reverse direction.

 

 

Second case (q3, λ), b replace by λ i.e. we pop b

 

Third case (q4, b), b store at stack as it is.

 

So, NPDA has more choices for moves, but DPDA has only one move possible.