PDAs: Empty Stack Acceptance and Conversions

Hello! Welcome back to our study of the Theory of Computation.

In the last lesson, we focused on designing Pushdown Automata (PDAs) that accept languages by final state. We saw how to devise a strategy using the stack for memory and translate that into the states and transitions of a PDA. The core condition was simple: after reading all input, the machine must be in one of its designated final states.

Today, we will explore an alternative, equally powerful method of acceptance: acceptance by empty stack. This lesson will cover three key objectives:

Formally define and design PDAs that accept by emptying their stack.
Learn the constructive algorithm to convert an empty-stack PDA into an equivalent final-state PDA.
Learn the reverse algorithm: converting a final-state PDA into an equivalent empty-stack one.

Mastering these conversions is not just a theoretical exercise; it proves a fundamental theorem: that both acceptance criteria define the exact same class of languages—the Context-Free Languages. The algorithmic nature of these conversions should resonate with your background in building complex systems, as it's akin to creating a compiler or transpiler that transforms one formal specification into another while preserving its behavior.

1. Acceptance by Empty Stack

While acceptance by final state ignores the final stack contents, acceptance by empty stack does the opposite: it ignores the final state, but the stack must be empty.

Formal Definition

Let's start with a formal definition. A PDA accepts a string w by empty stack if, starting from the initial configuration, it can process the entire string w and end up in any state with a completely empty stack.

Pushdown Automata 1 Formal Definition

This document, 'Pushdown Automata 1 Formal Definition' by Hoogeboom and Engelfriet, provides a clear and rigorous definition of the two acceptance types. We'll focus on the definition for empty stack.

Please read the section titled 'Computations' on page 2. Focus on the formal definition of the empty stack language, denoted as N(A). Contrast this with the definition of the final state language, L(A), which we discussed in the previous lesson.

As defined in the text, the empty stack language of a PDA $A$ is:
$N (A) = {w \in Σ^{*} ∣ (q_{in}, w, A_{in}) ⊢_{A}^{*} (λ, q, λ) for some q \in Q}$
The key components are:

The input w is fully consumed (leaving λ, the empty string).
The stack is completely empty (also λ).
The state q the machine ends in is irrelevant.

Designing for an Empty Stack

When designing a PDA for empty stack acceptance, the goal is to make the stack empty if and only if the input string belongs to the language. This often means popping the initial stack marker at the very end as the final step of acceptance.

Let's consider a language we've seen before: $L = {a^{n} b^{m} c^{n} ∣ n, m \geq 1}$ . In the last module, we would design a PDA for this that ends in a final state. Now, let's design one that accepts by empty stack.

Strategy:

Start with a symbol $Z_{0}$ on the stack.
For every a at the beginning of the string, push a symbol (e.g., X) onto the stack.
For the b's in the middle, do nothing with the stack (skip them).
For every c at the end, pop one X from the stack.
If we finish reading the input and the stack contains only $Z_{0}$ , it means the number of a's and c's matched. We can then add a final transition to pop $Z_{0}$ and empty the stack.

The following video shows a very similar strategy, though it's aimed at final state acceptance. Watch it to understand the core push/skip/pop logic.

Theory of Computation: PDA Example (a^n b^m c^n)

This video by Anita R demonstrates the PDA logic for a language very similar to ours. Focus on the core strategy of pushing for 'a's, ignoring 'b's, and popping for 'c's. We will then adapt this logic for empty stack acceptance.

Watch from the beginning until 04:51. Observe how the PDA uses the stack to ensure the count of 'a's matches the count of 'c's. Notice the final transition where the machine sees the bottom-of-stack marker.

To adapt the PDA shown in the video for empty stack acceptance, we would make a small but crucial change. Instead of the transition from q2 to a final state q3 that leaves the stack marker untouched (ε, Z / Z), we would define a transition that pops the marker:

Original (Final State): δ(q₂, ε, Z₀) = {(q_f, Z₀)}
Adaptation (Empty Stack): δ(q₂, ε, Z₀) = {(q_any, ε)}

This final pop empties the stack, thus accepting the string by our new criterion. If the input was malformed (e.g., too many c's or too few), the machine would either get stuck or end with a non-empty stack, leading to rejection.

2. Equivalence of Acceptance Criteria

A central result in automata theory is that the set of languages accepted by final state PDAs is the same as the set accepted by empty stack PDAs. We prove this by construction: providing an algorithm to convert a PDA of one type into an equivalent PDA of the other type.

The document Pushdown Automata 1 Formal Definition provides excellent, clear constructions for both directions of the proof.

Pushdown Automata 1 Formal Definition

We'll now study the two conversion algorithms that prove the equivalence of final-state and empty-stack PDAs.

Please read Section 2, 'Two Families' (pages 4-5), which contains Lemma 6. This section details the two constructions. Focus on the diagrams and the bullet points describing the new transitions added in each case.

Let's break down these two constructions.

Construction 1: From Empty Stack (N) to Final State (L)

Goal: Given a PDA $A_{N}$ that accepts by empty stack, construct a PDA $A_{F}$ that accepts the same language by final state.

Intuition: The new machine $A_{F}$ will simulate $A_{N}$ . But how can $A_{F}$ know when $A_{N}$ 's stack would have become empty? We give it a special "canary" symbol at the bottom of its stack. When $A_{F}$ sees this symbol, it knows $A_{N}$ 's stack is empty and can transition to a final state.

Algorithm:

Create a new start state $q_{in}^{'}$ and a single new final state $q_{f}$ .
Introduce a new bottom-of-stack symbol $□$ that is not in the original stack alphabet.
Initialization: Add a transition from $q_{in}^{'}$ that does not read input. It pushes the original start symbol $A_{in}$ and the new marker $□$ onto the stack, then moves to the original start state $q_{in}$ .
- δ'(q'_{in}, ε, □) = {(q_{in}, A_{in}□)} (Note: we assume the machine starts with □ on the stack for this transition).
Simulation: Copy all transitions from the original PDA $A_{N}$ to $A_{F}$ .
Acceptance: For every state q in the original PDA, add a transition to the new final state q_f. This transition consumes no input and is only possible when the special marker $□$ is at the top of the stack.
- δ'(q, ε, □) = {(q_f, ε)} for all q ∈ Q_N.

This construction ensures that $A_{F}$ can only reach its final state precisely when $A_{N}$ would have emptied its stack.

Construction 2: From Final State (L) to Empty Stack (N)

Goal: Given a PDA $A_{F}$ that accepts by final state, construct a PDA $A_{N}$ that accepts the same language by empty stack.

Intuition: The new machine $A_{N}$ will simulate $A_{F}$ . Whenever $A_{F}$ has the option to enter a final state, we give $A_{N}$ a new option: jump to a special "stack-emptying" state. This state has a loop that will pop everything off the stack.

Algorithm:

Create a new start state $q_{in}^{'}$ and a new "emptying" state $q_{e}$ . The new PDA will have no final states.
Introduce a new bottom-of-stack symbol $□$ . This prevents the simulation from accidentally emptying the stack before acceptance.
Initialization: Add a transition from $q_{in}^{'}$ that pushes the original start symbol $A_{in}$ and the new marker $□$ , then moves to the original start state $q_{in}$ .
- δ'(q'_{in}, ε, □) = {(q_{in}, A_{in}□)}
Simulation: Copy all transitions from the original PDA $A_{F}$ to $A_{N}$ .
Emptying:
- For every final state q in the original PDA $A_{F}$ , add an ε-transition to the new emptying state q_e. This transition pops nothing and pushes nothing (i.e., it leaves the stack top as is). This is the choice to accept.
  - δ'(q, ε, A) = {(q_e, A)} for all q ∈ F and for every stack symbol A.
- Add a loop on state q_e. This loop will pop every symbol off the stack without reading input.
  - δ'(q_e, ε, A) = {(q_e, ε)} for every stack symbol A (including the new marker $□$ ).

This allows the new PDA to nondeterministically decide to empty its stack whenever the original PDA would have reached an accepting state.

3. Applying the Conversion

Let's put the second construction into practice.

Test your understanding!

Consider the following PDA that accepts by final state (q2). Its language is strings with more a's than b's.

Apply the algorithm to transform this final-state PDA into an equivalent empty-stack PDA. Describe the new states and transitions you would add.

Show answer

Let's apply the Final State -> Empty Stack construction.

Original PDA (A_F):

States: $Q_{F} = {q_{0}, q_{1}, q_{2}}$
Final States: $F = {q_{2}}$
Stack Alphabet: $Γ_{F} = {A, B, X}$ (where X is the initial symbol)

New PDA (A_N):

New States: We add a new start state $q_{in}^{'}$ and a new emptying state $q_{e}$ .
- New set of states: $Q_{N} = {q_{0}, q_{1}, q_{2}, q_{in}^{'}, q_{e}}$
New Stack Symbol: We add a new bottom-of-stack marker, let's call it $□$ .
- New stack alphabet: $Γ_{N} = {A, B, X, □}$
New Transitions:
- Initialization: Add a transition from $q_{in}^{'}$ to $q_{0}$ :
  - δ(q'_{in}, ε, □) = {(q_0, X□)}
    (This assumes we can define the PDA to start with $□$ on the stack. An alternative is δ(q'_{in}, ε, Z) = {(q_0, XZ)} for any initial stack symbol Z and then adjusting the transitions accordingly, but the new-marker approach is cleaner).
- Simulation: All original transitions from the diagram are copied over. For example:
  - δ(q_0, a, X) = {(q_0, AX)}
  - δ(q_0, b, A) = {(q_1, ε)}
  - ...and so on.
- Emptying Trigger: Since q2 is the only final state, we add ε-transitions from q2 to q_e for every possible symbol on top of the stack.
  - δ(q_2, ε, A) = {(q_e, A)}
  - δ(q_2, ε, B) = {(q_e, B)}
  - δ(q_2, ε, X) = {(q_e, X)}
  - δ(q_2, ε, □) = {(q_e, □)}
- Emptying Loop: Add a universal pop loop on state q_e.
  - δ(q_e, ε, A) = {(q_e, ε)}
  - δ(q_e, ε, B) = {(q_e, ε)}
  - δ(q_e, ε, X) = {(q_e, ε)}
  - δ(q_e, ε, □) = {(q_e, ε)}

The resulting PDA, $A_{N}$ , has no final states but will accept the exact same language by emptying its stack.

Conclusion

Today we've expanded our understanding of Pushdown Automata significantly. We have not only learned a new method of acceptance but have also formally proven that it is just as powerful as the one we already knew.

Key Takeaways:

A PDA can accept a language by empty stack, which occurs when the entire input is consumed and the stack is left empty.
We can design PDAs specifically for this criterion, often by ensuring the initial stack marker is popped as the final step.
Acceptance by final state and acceptance by empty stack are equivalent. We proved this by providing two constructive algorithms:
1. How to convert an empty-stack PDA to a final-state one.
2. How to convert a final-state PDA to an empty-stack one.

Preview of the Next Lesson:
We have now established two equivalent formalisms for recognizing Context-Free Languages: PDAs that accept by final state, and PDAs that accept by empty stack. In the next lesson, we will complete the picture by formally connecting automata back to grammars. We will learn the algorithm to convert any Context-Free Grammar (CFG) into an equivalent PDA. This will demonstrate that PDAs are precisely the machines that recognize the languages generated by CFGs, solidifying the fundamental link between these two concepts.

Recommended resources