An Overview of Pushdown automata (PDA)

Let's take a look at the context-free language L={aⁿbⁿ | 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.

Table of Contents

1. Informal Definition
2. Formal Definition
3. Stack Manipulation
4. Non-deterministic VS. Deterministic PDAs
5. Example

Informal Definition

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:

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.

Formal Definition

Non-deterministic Push-Down Automaton is a septuple M = (Q, Σ, Γ, δ, q₀, Z, F) where Q is a finite set of states
Σ is a finite input alphabet
Γ is a finite stack alphabet
q₀ 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 × Γ^* is a transition function.

Language accepted by a PDA M = (Q, Σ, Γ, δ, q₀, Z, F) is the set L(M) = {w ∈ Σ^* | (q₀, w, Z) ⊢^∗ (p, λ, u), p ∈ F, u ∈ Γ^∗}

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

Stack Manipulation

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 (i.e. we only care about the top of the stack)!

x	Before	After	Meaning
λ			Pop the top of the stack
B			Replace "A" with "B"
BA			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.

Non-deterministic VS. Deterministic PDAs

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
   

2. If δ(q, λ, b) is not empty, then δ(q, a, b) = Ø for all a ∈ Σ, so the following is prohibited in DPDAs
   

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

Example

Let's take the language L={wcw^R | w ∈ (a+b)^∗} 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^R string has occurred.

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

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- Pushdown Automata: PDA-DPDA by Robert M. Kline
2- Pushdown Automata by Brilliant
3- An Introduction to Formal Languages and Automata by Peter Linz