What is a pushdown automaton?

A pushdown automatonPlural: Automata (PDA) presents a context-free language. A PDA is a finite state machine that has a memory in the form of a stack. We can add elements to the stack to access them for future use.

A PDA's components

A PDA consists of three main components:

• An input string or tape
• A finite control unit
• A stack for memory

The stack has two functions: push and pop. At every step, the PDA makes a decision to push an element from the input, or pop an element from the stack. The stack contains a starting/stopping symbol ($ or Z) that indicates the end of a stack.

A PDA is a 7-tuple automata $(Q ,∑ ,Γ ,q0 ,δ, Z0, F )$. It includes the following:

• $Q$: A set of states
• $∑$: A set of input symbols
• $Γ$: A set of the stack elements
• $q0$: An initial state
• $δ$: A transition function, that is, the condition that allows the state to change
• $Z0$: The initial/end stack element
• $F$: A set of final states

Transition notations in PDA

There are several notations to show transitions. The following graph shows one of these transition notations in PDA:

Where $x$ is the input, $Z0$ is the top of the stack element. The action we need to take is specified after the "/" sign. The two actions can be as follows:

• $y$ is the top two elements of the stack in the case of a push operation
• ^ specifies to pop, the topmost element of the stack

Note: It is not necessary to consume the input to move to another state. We can also make a transition non-deterministically (a null transition) where $x$ is ^.

Turnstile notations

The turnstile notation shows a transition without a graph. It uses instantaneous description (ID) to do so.

IDs include $q$, $w$, and $s$, where:

• $q$ is the state
• $w$ is the remaining input
• $s$ is the stack contents

For example, $(q1, ab, aZ0) ⊢ (q2, b, aaZ0).$

In this transition, the state changes from $q1$ to $q2$ by consuming the input $a$. Also, the input is pushed into the stack.

Examples

Let's see a few examples to clarify things further:

Palindromes

We can't specify palindromes A palindrome is a word, number, or sentence that reads the same backward and forward. For example, "wow" and "565."with a deterministic finite automaton (DFA) because they require memory. A PDA, however, remembers the elements that must be compared.

Let's suppose $L = (SS' | ScS’, S=(a, b)^*)$, where $L$ is a palindrome of an even or odd length.

The PDA above is a non-deterministic PDA that can make a null or epsilon transition. Here, the PDA keeps pushing the elements into the stack.

In the case of an even palindrome, it stops until the first half of the input is consumed. In the case of an odd palindrome, it looks for element $c$.

The PDA then compares the input with the stack elements and pops them if it finds a match. At the end of the input, if the stack only contains $Z0$, then the string is considered a palindrome.

The or condition

We now look at a slightly complex example.

Let's suppose the following: $\space L= {a^ib^jc^k | i \neq j \ \mathrm{or} \ i \neq k}$

As the language contains an or condition, the states change non-deterministically. That is, the $q0$ path changes to the $q1$ path, or the $q0$ path changes to the $q4$ path.

In the path above, the number of $a$s should not equal the number of $b$s.

• The $a$s are pushed on the stack one by one, and popped against the $b$s.
• If the stack becomes empty, even though $b$s are left in the input or $a$s remain in the stack, the string is accepted.
• The $c$s are just consumed without any action, as they are irrelevant to these types of strings.

In the path below, the number of $a$s should not equal the number of $c$s.

• The $a$s are pushed on the stack one by one, and the $b$s are consumed without any action or change to the stack. This is because these are irrelevant to the strings.
• As the input reaches the $c$s, the $a$s are popped against the $c$s. It checks whether the $c$s are left in the input, or if the $a$s remain in the stack. If so, the string is accepted.