PushDown Automaton transitions

A PushDown Automaton (PDA) is a six tuple $(Q, \Sigma, \Gamma, \delta, q_0, F)$ where

$Q$ is a finite set of states

$\Sigma$ is a finite input alphabet

$\Gamma$ is a finite stack alphabet

$q_0 \in Q$ is the start state

$F \subseteq Q$ is the set of final/accepting states

Transition Function

The transition function $\delta$ is mapped as follows

$\begin{equation*} Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q \times (\Gamma \cup \{\epsilon\})) \end{equation*}$

The terms on the left correspond to the current state, the input symbol being read and the symbol on top of the stack being popped.

The terms on the right correspond to the new state and the symbol pushed to the top of the stack.

The powerset allows multiple choices. Read/pop/push all allow $\epsilon$ . Thus, these transitions are non-deterministic in nature.

Example

An example PDA transition is given below

Here $a$ is the symbol being read, $x$ is popped from the top of the stack and $y$ is pushed onto the top of the stack.

Keep in mind that the conditions to the left of the arrow must be satisfied for the transition to take place. In other words, while reading a string, if I see the symbol $a$ and the top of the stack is $x$ , I can follow the transition by reading the $a$ , removing the $x$ from the stack and pushing the $y$ onto the stack.

Any of $a$ , $x$ and $y$ can be $\epsilon$ . Think of $\epsilon$ as the absence of something – don’t care about that operation.

Do not read, do pop, do push

Do not read anything. Pop $x$ from the top of the stack. Push $y$ onto the stack.

Do read, do not pop, do push

Read the input symbol $a$ . Ignore the top of the stack. Push $y$ onto the stack.

Do read, do pop, do not push

Read the input symbol $a$ . Pop $x$ from the top of the stack. Do not push anything to the stack.

Do not read, do not pop, do not push

This is similar to an $\epsilon$ transition in NFAs where you are just changing states. No symbol is read and the stack is not modified.

The Beard Sage