PUSH DOWN AUTOMATION:

A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

Basically a pushdown automaton is −

“Finite state machine” + “a stack”

A pushdown automaton has three components −

an input tape,
a control unit, and
a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack does two operations −

Push − a new symbol is added at the top.
Pop − the top symbol is read and removed.

We use standard formal language notation: $\Gamma ^{*}$ denotes the set of strings over alphabet $\Gamma$ and $\varepsilon$ denotes the empty string.

A PDA is formally defined as a 7-tuple:

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$ where

$\,Q$ is a finite set of states
$\,\Sigma$ is a finite set which is called the input alphabet
$\,\Gamma$ is a finite set which is called the stack alphabet
$\,\delta$ is a finite subset of $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$ , the transition relation.
$\,q_{0}\in \,Q$ is the start state
$\ Z\in \,\Gamma$ is the initial stack symbol
$F\subseteq Q$ is the set of accepting states

An element $(p,a,A,q,\alpha )\in \delta$ is a transition of $M$ . It has the intended meaning that $M$ , in state $p\in Q$ , on the input $a\in \Sigma \cup \{\varepsilon \}$ and with $A\in \Gamma$ as topmost stack symbol, may read $a$ , change the state to $q$ , pop $A$ , replacing it by pushing $\alpha \in \Gamma ^{*}$ . The $(\Sigma \cup \{\varepsilon \})$ component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.

PUSH DOWN AUTOMATION:

Share this: