Designing PDAs for Final State Acceptance

1. The Core Strategy: Stack as Memory

The power of a PDA over a Finite Automaton comes from its stack. The central question in designing any PDA is: "What information must be remembered to verify a string, and how can the stack store and retrieve this information?"

Here are some common strategies:

• Counting and Matching: Use the stack to count occurrences of a symbol in one part of the string, then match them against another symbol in a later part. The classic example is a language like $L=\{a^n{b}^n\}$.
• Storing and Reversing: Push the characters of the first part of a string onto the stack. Since the stack is a Last-In, First-Out (LIFO) structure, popping the characters will naturally produce them in reverse order, which is perfect for recognizing palindromic languages like $L=\{w{w}^R\}$.
• Maintaining a Balance: Use the stack to track a running balance between two types of symbols. For instance, pushing for symbol a and popping for symbol b can verify properties related to the relative counts of as and bs.

A key convention in PDA design is to use a bottom-of-stack marker (often denoted $Z_0$ or $ symbol). This symbol is pushed onto the empty stack at the very beginning of the computation. It serves two main purposes:

1. It lets the PDA know when it has popped all the symbols it previously pushed, allowing it to recognize that the "working" part of the stack is empty.
2. It prevents the machine from crashing if it needs to perform a transition on an empty stack before the computation is complete.

2. Formal Definition of Acceptance

Before we start designing, let's quickly formalize what "acceptance by final state" means. As you'll recall from our last lesson, a PDA is a 7-tuple $M=(Q,\Sigma ,\Gamma ,q_0,Z_0,A,\delta )$.

The following resource provides a concise formal definition. Please review the definitions for a PDA, its configuration (which we called an ID), and what it means for a string to be accepted by final state.

The key takeaway is that for a string to be accepted, the PDA must consume the entire input string (ending with Λ or ε remaining) and halt in an accepting state (q ∈ A). The final content of the stack (α) does not matter for this acceptance criterion.

3. Design Walkthrough 1: A Counting Language

Let's design a PDA for the canonical context-free language: $L=\{0^n{1}^n\mid n\ge 0\}$.

The Strategy:

1. Initialize the stack by pushing a bottom marker, $Z_0$.
2. Read the first part of the string. For every 0 we see, we push a symbol (e.g., another 0) onto the stack. This effectively counts the number of 0s.
3. When we see the first 1, we switch from pushing to popping.
4. For every 1 we read, we pop one 0 from the stack.
5. If we finish reading the input string exactly when the stack becomes empty (i.e., we see our marker $Z_0$), we can move to an accepting state.

The following video provides an excellent walkthrough of this design process, focusing on the reasoning behind each state and transition.

As you saw, the design translates our strategy directly into a state machine with stack operations. The machine uses different states to keep track of which part of the pattern it's currently processing (pushing 0s vs. popping for 1s).

4. Design Walkthrough 2: A Palindromic Language

Now let's tackle a language that requires non-determinism: $L=\{w{w}^R\mid w\in \{a,b{\}}^{\ast }\}$, the language of even-length palindromes.

The Strategy:
The challenge here is that the PDA doesn't know where w ends and w^R begins. This is where non-determinism comes to the rescue.

1. Push the symbols of the first half of the string, w, onto the stack.
2. Non-deterministically guess that we have reached the middle of the string. This is modeled by an ε-transition that doesn't consume any input.
3. Switch to a "popping" mode.
4. For the second half of the string, w^R, match each incoming symbol with the symbol popped from the stack. Because the stack is LIFO, it will naturally provide the characters of w in reverse order.
5. If the input is finished and the stack is empty (down to the marker), accept.

For any string in $L$, there will be exactly one computational path where the non-deterministic "guess" is made at the right time, leading to acceptance. For any string not in $L$, no path will succeed.

Let's look at a diagram for this PDA.

Here's how to interpret the diagram:

• State q0 (Grow stack): While in this state, the PDA reads input symbols (a or b) and pushes them onto the stack.
• The ε transition (Switch to popping mode): The arrow from q0 to q1 labeled ε, Z / Z represents the non-deterministic guess. At any point, without consuming input, the machine can jump to q1. (Note: a more general notation would be ε, X / X for any stack symbol X, as the switch can happen anytime).
• State q1 (Pop stack for matching symbols): In this state, the machine must match the input symbol with the symbol at the top of the stack and pop it.
• Transition to q2 (Go to acceptance): Once the input is consumed, if the stack only contains the initial marker Z, the machine can move to the final state q2 and accept.

5. A Quick Refresher on Graphical Notation

You've seen a few diagrams now. The notation for transitions is crucial. Let's ensure it's perfectly clear.

A transition label a, b / c means:

1. a: Read a from the input tape. If a is ε, do not read any input.
2. b: The symbol b must be on top of the stack. Pop b.
3. c: Push the string c onto the stack. If c is ε, nothing is pushed.

The following short video segment clearly explains this convention.

Conclusion

Today we've moved from being analysts to being architects of Pushdown Automata. You've learned how to devise a strategy for computation and translate it into the formal language of states and stack operations.

Key Takeaways:

• PDA design is strategy-driven, focused on using the stack as a specific kind of memory (LIFO).
• Common strategies involve using the stack for counting, matching, and reversing substrings.
• The bottom-of-stack marker ($Z_0$) is a vital tool for initializing the process and detecting when the "working" part of the stack is empty.
• Non-determinism is a powerful tool for handling languages where the structure is ambiguous, such as guessing the midpoint of a palindrome.
• For acceptance by final state, the goal is to consume all input and end in an accepting state, regardless of the final stack contents.

Preview of the Next Lesson:
We've focused entirely on acceptance by final state. However, there is another, equivalent method for a PDA to accept a language: acceptance by empty stack. In our next lesson, we will explore this second criterion, learn how to design PDAs that use it, and, crucially, prove that the two methods of acceptance are equivalent in power by showing how to convert a PDA of one type into the other.