Theory

Pushdown Automata (PDA)

A push down automata (PDA) is a way to implement a context free grammar (CFG) in a similar way to design the deterministic finite automata (DFA) for a regular grammar.A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

PDA= "Finite state machine" + "a stack"
PDA has three components, which are as follows −

An input tape.

A control unit.

A stack with infinite size.

A stack does two operations −

Push − a new symbol is added at the top.

Pop − the top symbol is read and removed.

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) −

Q is the finite number of states

∑ is input alphabet

S is stack symbols

δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*

q0 is the initial state (q0 ∈ Q)

I is the initial stack top symbol (I ∈ S)

F is a set of accepting states (F ∈ Q)

PDA Components:

Input tape: The input tape is divided in many cells or symbols. The input head is read-only and may only move from left to right, one symbol at a time.

Finite control: The finite control has some pointer which points the current symbol which is to be read.

Stack: The stack is a structure in which we can push and remove the items from one end only. It has an infinite size. In PDA, the stack is used to store the items temporarily.