FOR FREE MATERIALS

Push Down Automata (PDA)

PDA: Introduction

Push Down Automata(PDA):

PDA consists of 7 tuples:

M = {Q, ∑, Г, δ, ${\mathbf{q}}_{\mathbf{0}}$, z, F}

Q – denotes a finite set of states.

∑ – denotes a finite set of input symbols.

Г – denotes a finite set of pushdown symbols or stack symbols.

δ – denotes the transition functions.

${\mathbf{q}}_{\mathbf{0}}$ – is the initial state (${\mathbf{q}}_{\mathbf{0}}$ ∊ Q)

z  –  is the stack bottom symbol.

F  –  is the final state of the PDA.

Diagram of Push Down Automata:

PDA has Infinite memory inform of stack.

This machine define that read input from input tape and take Top of the Stack (TOS) symbol and decide move as per present state. So, move depends on present state, input and TOS.

Here input tape is read only but R/W at stack is Read / Write both

This machine works if we used z at starting symbol of stack because z is taking as safety purpose.

Moves depends on δ(q, a, α) when Г = {z, α, β }, ∑ = {a, b}, ∑ ⊄ Г

Here output alphabet Г and input alphabet ∑ may be same or not.

Let ∑ = {a, b} and Г = {a, b, z} so, here ∑ ⊆ Г.     

Here both NPDA and DPDA allowed λ – transition i.e. a move does not contain any input symbol i.e. Q X λ X Г.

PDA has two types:

1. Deterministic Push Down Automata (DPDA)

2. Non-Deterministic Push Down Automata (NPDA)

First we define dead configuration:

Dead Configuration: $\mathbf{(}{\mathbf{q}}_{\mathbf{1}}\mathbf{,}\mathbf{ }\mathbf{a}\mathbf{,}\mathbf{ }\mathbf{b}\mathbf{)}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\varphi }$ (There is no move) – Possible for both NPDA and DPDA.