The 7-Tuple Definition of a Pushdown Automaton (PDA)

1. Why We Need More Than Finite Automata

Let's start with a foundational question: why are finite automata not enough? Consider the classic context-free language $L=\{a^n{b}^n\mid n\ge 0\}$. To recognize strings in this language (e.g., aaabbb), a machine must ensure the number of a's perfectly matches the number of b's. This requires counting the a's, which implies some form of memory.

A finite automaton's memory is limited to its current state. It cannot remember an unbounded count of symbols. To solve this, we augment the finite automaton with a stack—a simple, yet powerful, memory device.

The following video provides an excellent intuitive build-up, explaining the limitations of FAs and introducing the stack as the natural solution. Your background in software development means you're already very familiar with stack data structures (LIFO - Last-In, First-Out), so the core concept should feel quite natural.

2. The Formal Definition of a Pushdown Automaton

Now that we have the intuition, let's formalize it. A Pushdown Automaton is defined by seven components, captured in a 7-tuple.

As the diagram shows, a PDA extends an NFA with a stack. Three of the seven components are entirely new and relate to this stack.

To get a clear, textual breakdown of these components, please read the following section from the article "Advanced Automata Theory — Week 4".

Let's summarize the 7-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$:

• $Q$: A finite set of states. (Same as in an FA)
• $\Sigma$: A finite set called the input alphabet. (Same as in an FA)
• $\Gamma$: A finite set called the stack alphabet. These are the symbols that can be pushed onto the stack. This is a new component.
• $\delta$: The transition function, which we will explore in detail next.
• $q_0\in Q$: The start state. (Same as in an FA)
• $Z_0\in \Gamma$: The initial stack symbol. This symbol is on the stack at the very beginning of computation. It often serves as a marker for an empty stack. This is a new component.
• $F\subseteq Q$: The set of accepting or final states. (Same as in an FA)

The power of the PDA comes from the three new elements: the stack alphabet $\Gamma$, the initial stack symbol $Z_0$, and, most importantly, the new, more powerful transition function $\delta$.

3. The Heart of the PDA: The Transition Function $\delta$

The transition function is what drives the PDA. Unlike in an FA, where a transition only depends on the current state and input symbol, a PDA's transition also depends on the symbol at the top of the stack.

The formal signature of the transition function is:
$\delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma \to {\mathcal{P}}_{\text{finite}}(Q\times {\Gamma }^{\ast })$
Let's decode this:

• Input to $\delta$: A triplet (state, input symbol or ε, stack-top symbol).

  • state \in Q: The current state of the machine.
  • input symbol or ε \in (\Sigma \cup \{\varepsilon\}): The next symbol on the input tape, or ε if we're making a move without consuming input.
  • stack-top symbol \in \Gamma: The symbol currently at the top of the stack.

• Output of $\delta$: A finite set of pairs {(next_state, string_to_push), ...}.

  • next_state \in Q: The state the machine will transition to.
  • string_to_push \in \Gamma^*: The string of symbols that will replace the symbol that was just read from the stack. The symbol that was on top is effectively popped, and this new string is pushed in its place. The first symbol of this string becomes the new top of thestack.

Key Stack Operations:
The string_to_push (let's call it $\gamma$) determines the stack operation:

1. Push: If $\gamma$ is a string of length 2 or more (e.g., AB), the original top symbol is replaced by multiple symbols. This grows the stack.
2. No Change: If $\gamma$ is a single symbol (e.g., A), the original top symbol is replaced by one symbol. The stack size is unchanged.
3. Pop: If $\gamma$ is the empty string, $\epsilon$, the original top symbol is removed and not replaced. This shrinks the stack.

The following video segment provides a detailed walkthrough of the transition function, illustrating how to interpret its notation.

Conclusion

In this lesson, we have formally defined the Pushdown Automaton, the machine model for recognizing context-free languages. We've seen how it enhances a finite automaton with a stack, providing it with the memory needed to handle more complex language structures.

Key Takeaways:

• A Pushdown Automaton (PDA) is essentially a nondeterministic finite automaton augmented with a stack.
• The formal definition of a PDA is a 7-tuple: $(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, where $\Gamma$, $Z_0$, and the more complex $\delta$ function are the key additions.
• The transition function $\delta$ is the core of the PDA's operation. Its behavior is determined by the current state, the current input symbol (or $\epsilon$), and the symbol at the top of the stack.
• A single transition involves popping the top stack symbol and pushing a new string of symbols, allowing for push, pop, or no-change operations on the stack.

Preview of the Next Lesson:
Now that we understand the formal structure of a PDA, our next step is to put it into practice. In the next lesson, we will learn how to trace the execution of a PDA on an input string, using instantaneous descriptions to track the machine's configuration and determine whether a string is accepted or rejected.