FOR FREE MATERIALS

DPDA and NPDA:

Definition of DPDA:

M = {Q, ∑, Г, δ, ${\mathbf{q}}_{\mathbf{0}}$, 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 ${\mathbf{q}}_{\mathbf{0}}$ 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, ∑, Г, δ, ${\mathbf{q}}_{\mathbf{0}}$, 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 $\mathbf{Q}\mathbf{ }\mathbf{\to }\mathbf{ }\mathbf{(}{\mathbf{q}}_{\mathbf{0}}\mathbf{,}\mathbf{ }{\mathbf{q}}_{\mathbf{1}}\mathbf{)}$ 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 $\mathbf{(}{\mathbf{q}}_{\mathbf{3}}\mathbf{,}\mathbf{ }\mathbf{\lambda }\mathbf{)}$, b replace by λ i.e. we pop b

Third case $\mathbf{(}{\mathbf{q}}_{\mathbf{4}}\mathbf{,}\mathbf{ }\mathbf{b}\mathbf{)}$, b store at stack as it is.

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