A PushDown Automaton (PDA) is a six tuple where

is a finite set of states

is a finite input alphabet

is a finite stack alphabet

is the start state

is the set of final/accepting states

## Transition Function

The transition function is mapped as follows

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 . Thus, these transitions are non-deterministic in nature.

## Example

An example PDA transition is given below

Here is the symbol being read, is popped from the top of the stack and 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 and the top of the stack is , I can follow the transition by reading the , removing the from the stack and pushing the onto the stack.

Any of , and can be . Think of as the absence of something – don’t care about that operation.

## Do not read, do pop, do push

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

## Do read, do not pop, do push

Read the input symbol . Ignore the top of the stack. Push onto the stack.

## Do read, do pop, do not push

Read the input symbol . Pop 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 transition in NFAs where you are just changing states. No symbol is read and the stack is not modified.