An Overview of Pushdown automata (PDA)
Published: 2019-12-24 11:31:50

Let's take a look at the context-free language L={a<sup>n</sup>b<sup>n</sup> | n ≥ 1}. How can we design a finite automaton (i.e. DFA/NFA) that accepts this language? To design a finite automaton that accepts this language, we should store the number of a's in some sort of memory in order to compare it to the number of b's. However, this's impossible due to the non-existence of memory in finite automata.

In this post, i'm going to walk you through the concept of PDAs and tackle how we can design machines that accept context-free languages.

<h2>Table of Contents</h2>
1. <a href="#title1">Informal Definition</a>
2. <a href="#title2">Formal Definition</a>
3. <a href="#title3">Stack Manipulation</a> 
4. <a href="#title4">Non-deterministic VS. Deterministic PDAs</a>
5. <a href="#title5">Example</a>

<h2 id="title1">Informal Definition</h2>

Let's think of PDAs as finite automata with a memory. This memory is simply a stack that can be manipulated as a part of the finite automata moves. The stack has initially a single symbol at the bottom of it which is denoted by Z (can be different in various textbooks).


Transitions in PDAs are of the form δ(q, a, A) contains (p, x) which means when you're in state q, if you see 'a' on input and A on top of stack:
• Go to state p
• Replace A on the stack with the string x (leftmost symbol of x is on top of the stack). Here's the above transition depicted:
![Transition simulation](https://thepracticaldev.s3.amazonaws.com/i/3czmztr3x42grzhwun0n.gif)
Note that the colored parts in the stack indicate strings.

An input string is accepted if after the entire string is read, the PDA reaches a final state. It's important to mention that the stack contents are irrelevant to the acceptance of the string.

<h2 id="title2">Formal Definition</h2>

Non-deterministic Push-Down Automaton is a septuple M = (Q, Σ, Γ, δ, q<sub>0</sub>, Z, F) where Q is a finite set of states
Σ is a finite input alphabet
Γ is a finite stack alphabet
q<sub>0</sub> is the start state
Z ∈ Γ is the stack start symbol
F ⊆ Q is the set of final states
δ : Q × Σ U {λ} × Γ → finite set of subsets of Q × Γ<sup>*</sup> is a transition function.

Language accepted by a PDA M = (Q, Σ, Γ, δ, q<sub>0</sub>, Z, F) is the set L(M) = {w ∈ Σ<sup>*</sup> | (q<sub>0</sub>, w, Z) &#8866;<sup>&lowast;</sup> (p, λ, u), p ∈ F, u ∈ Γ<sup>&lowast;</sup>}

The PDA accepts all strings w for which you can reach the final
state at the end of the string <strong>(the stack contents are irrelevant)</strong>.

<h2 id="title3">Stack Manipulation</h2>

Let's say we have the following transition: δ(q, a, A) contains (p, x). The following table demonstrates how we'd manipulate the stack by replacing the x symbol by others. Note that A and B are single symbols and not strings and the red portion indicates that the stack contents can be anything <strong>(i.e. we only care about the top of the stack)!</strong>

| x | Before | After | Meaning |
| --------- |:---------:| :-------: | -------:| 
| λ | ![Stack with an "A" symbol on the top](https://thepracticaldev.s3.amazonaws.com/i/m50a84fwhqkubo7gpje8.png) | ![Same stack as the initial one with the symbol "A" removed](https://thepracticaldev.s3.amazonaws.com/i/6l8lolfykpy4jkzpj854.png) | Pop the top of the stack | 
| B | ![Stack with an "A" symbol on the top](https://thepracticaldev.s3.amazonaws.com/i/m50a84fwhqkubo7gpje8.png) | ![Same stack as the initial one with the symbol "A" replaced with the symbol "B"](https://thepracticaldev.s3.amazonaws.com/i/kmc61wcj6igy322o7du7.png) | Replace "A" with "B" |
| BA | ![Stack with an "A" symbol on the top](https://thepracticaldev.s3.amazonaws.com/i/m50a84fwhqkubo7gpje8.png) | ![Same stack as the initial one with the symbol "B" on top of the symbol "A"](https://thepracticaldev.s3.amazonaws.com/i/xvo2c9nsfif1li9s09yl.png) | Push "B" on the top of "A" |

How do we write the transition on the PDA graph? The answer is: 
symbol you read, top of the stack, stack manipulation.
Example: a, A, B which means if you read an "a" and the top of the stack is "A", go to the state that the transition arrow points to and replace the "A" with "B" in the stack.

<h2 id="title4">Non-deterministic VS. Deterministic PDAs</h2>

The only difference between NPDAs and DPDAs is that the latter has two restrictions: 
1. δ(q, a, b) contains at most one element, so the following is prohibited in DPDAs
![Prohibited transition 1](https://thepracticaldev.s3.amazonaws.com/i/222wwznkcf2kh46cn5dz.png)

2. If δ(q, λ, b) is not empty, then δ(q, a, b) = Ø for all a ∈ Σ, so the following is prohibited in DPDAs
![Prohibited transition 2](https://thepracticaldev.s3.amazonaws.com/i/8qtzequ5tggizi2srsfx.png)

Unlike finite automata , <strong>not every NPDA has an equivalent DPDA.</strong> Therefore, the class of deterministic and non-deterministic languages are not equivalent.

<h2 id="title5">Example</h2>

Let's take the language L={wcw<sup>R</sup> | w ∈ (a+b)<sup>&lowast;</sup>} as an example. The general approach to design an NPDA for this language is to push all symbols you encounter until you encounter the symbol c which is a sign that the reverse string must occur. Then your NPDA should compare what is on the stack to what is being read until the stack is empty which is a sign that the w<sup>R</sup> string has occurred.

Here's the NPDA design with a simulation for the input string abcba:

![NPDA design for the given language](https://thepracticaldev.s3.amazonaws.com/i/wx7g7ory30h60hopmzsj.gif)

At the end of this post, I'd like to suggest a few resources that I think would be helpful if you want to acquire more knowledge about Pushdown automata:
1- <a href="https://www.cs.wcupa.edu/rkline/fcs/pdas.html">Pushdown Automata: PDA-DPDA by Robert M. Kline</a>
2- <a href="https://brilliant.org/wiki/pushdown-automata/">Pushdown Automata by Brilliant</a>
3- <a href="https://books.google.com.sa/books/about/An_Introduction_to_Formal_Languages_and.html?id=hsxDiWvVdBcC&printsec=frontcover&source=kp_read_button&redir_esc=y#v=onepage&q&f=false">An Introduction to Formal Languages and Automata by Peter Linz</a>