Pushdown Automaton

A pushdown automaton (PDA) is an automaton that extends a finite state machine by adding memory in the form of a stack. It can interpret context-free grammars.

Recall that the main limitation of FSAs is that they are memoryless, that is, they cannot count or keep any past information from previous states. PDAs aim to fix this by allowing a stack with unlimited memory. The restriction now is that memory can only be access in a LIFO (last in first out) order.

Like finite state automata, a PDA can be both deterministic (DPDA) or non-deterministic (NPDA), however, the most commonly used one is the non-deterministic version. This because, unlike finite automata, which have non-deterministic versions being equally as powerful as deterministic version, a non-deterministic PDA is strictly more powerful and a deterministic PDA. Equivalently, there are some NPDAs for which there is no equivalent DPDA.

Definition §

Non-deterministic Pushdown Automata (NPDA) ^definition-dfa

A (non-deterministic) PDA $P$ is defined as a 6-tuple:

$$P=(\Sigma ,\Gamma ,Q,q_0,\delta ,F)$$

• $\Sigma$ = An input alphabet
• $\Gamma$ = The stack alphabet, which can be different from $\Sigma$.
• A set of states, $Q=\{q_1,q_2,\dots \}$
• An initial state, $q_0\in Q$
• A state transition function, $\delta$ which takes the current state ($q_{cur}$), the next character of the input string ($a$) and the symbol on the stack head ($x$), to return another state ($q_{next}$, and optionally pushes $y$ to the stack: $\delta :Q\times {\Sigma }_{ϵ}\times {\Gamma }_{ϵ}\to \mathcal{P}(Q\times {\Gamma }_{ϵ})\delta (q_{cur},a,x)=\{(q_{nex{t}_1},y),\dots \}$
• A set of accept states, $F\subseteq Q$

Behaviour §

• A PDA checks both the current symbol in the input string and the current symbol on the stack top (head). Hence, if either of them are not-defined in the transition function for the current state, the PDA automatically rejects the string.

%%🖋 Edit in Excalidraw, and the light exported image%%

• The stack can be non-empty when the machine ‘halts’ (accepts or rejects).

Stack Transitions §

If we look at the rightmost argument of the transition function $x$ and the optional $y$ that gets pushed to the stack:

$$\underset{\text{Popped from stack}}{\underbrace{x}}⟶\underset{\text{Pushed to stack}}{\underbrace{y}}$$

• So the PDA scans for $x$. If it sees $x$ at the top of the stack, it gets popped off and then $y$ gets pushed on to the stack

Epsilon Transitions §

We can also use $ϵ$ to not pop off $x$ or push $y$

• $ϵ\to x$ adds $x$ to the stack without removing anything off.
• $c\to ϵ$ removes $c$ without adding anything to the stack

%%🖋 Edit in Excalidraw, and the light exported image%%

Keeping Count §

Remember how finite automata are memoryless?, that is, they cannot remember any past states. For example, a finite automata can recognise the language $L=\{0^3{1}^3\}=000111$ by explicitly checking each character (using 6 states). It cannot however, recognise the language $L=\{0^n{1}^n|n\ge 0\}$, because by the time it gets to the 1’s, it has ‘forgotten’ how many zeroes were there before, so it cannot properly match the number of zeroes with the number of ones.

A PDA can use its stack to keep count of things, kind of. It cannot actually store a variable that increments, but it can match items. For example, take the language $L=\{0^n{1}^n\}$. To accept such a language, a PDA needs to be able to find equal amounts of 0’s and 1’s. We can do this by pushing 1’s onto the stack, and then whenever we encounter a 0, pop off a 1. If we end up with the stack being empty, we have an equal number of zeroes and ones.

To check if a stack is empty, we add a sentinel value at the beginning (this is because the stack alphabet can be different from the tape/input alphabet). Here, I’ve decided to use \$$ but the symbol can be anything. Then, just before the accept state, we check if the $$ is left in the stack.

%%🖋 Edit in Excalidraw, and the dark exported image%%

Conversion From CFG To PDA §

#todo Lecture 19

Theorems §

Example §

PDA that recognises $0^n{1}^n$

Find a PDA for the language below:

$$L=\{0^n{1}^n|n\in {\mathbb{N}}_0\}$$

Solution %%🖋 Edit in Excalidraw, and the light exported image%% This PDA works by adding $0$'s to the stack, and then removing one for each $1$ it encounters after. The very first state is an accept state so that it can accept $ϵ$ (given in $L$ when $n=0$)

Resources §

• A two-stack PDA is actually equivalent to a Turing Machine. See https://stackoverflow.com/questions/62083942/can-a-pda-with-two-stacks-accept-re-language#tosee okay, but if a NTM is as strong as a TM, but a NPDA is stronger than a DPDA, why does adding a second stack make the NPDA ‘weaker’?