Designing PDAs for Context-Free Languages

The Pushdown Automaton: An NFA with a Stack

A Pushdown Automaton (PDA) is essentially a non-deterministic finite automaton (NFA) equipped with a stack. This stack allows the machine to store and retrieve information, giving it a form of infinite memory, albeit with the restriction that it can only access the top element. This simple addition is what gives it the power to recognize context-free languages.

Formally, a PDA is a 7-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, where:

• Q: a finite set of states.
• $\Sigma$: a finite set for the input alphabet.
• $\Gamma$: a finite set for the stack alphabet.
• $q_0\in Q$: the start state.
• $Z_0\in \Gamma$: the initial symbol on the stack (often called the bottom-of-stack marker).
• $F\subseteq Q$: the set of final (or accepting) states.
• $\delta$: the transition function. This is the heart of the PDA. It takes the current state, an input symbol (or $ϵ$), and the symbol on top of the stack, and determines the next state and what to push onto the stack. $$\delta :Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to \mathcal{P}(Q\times {\Gamma }^{\ast })$$ A transition is written as $\delta (q,a,X)=\{(p,YZ)\}$. This means: "In state $q$, if the input is 'a' and the top of the stack is 'X', you can transition to state $p$, pop 'X', and push the string 'YZ' onto the stack (with 'Y' now at the top)." If we write $(p,ϵ)$, it means we just pop 'X' and push nothing.

Acceptance

There are two equivalent ways a PDA can accept a string:

1. Acceptance by Final State: After reading the entire input string, the PDA is in one of the final states ($F$). The contents of the stack do not matter.
2. Acceptance by Empty Stack: After reading the entire input string, the stack is empty. The state the PDA is in does not matter.

These models are equivalent, and you can convert a PDA that uses one method into a PDA that uses the other. For the GATE exam, you should be familiar with both, as a problem may specify either one.

Intuitive Design: Solving the $a^n{b}^n$ Problem

Let's design a PDA for the language that started our discussion of context-free languages: $L=\{a^n{b}^n\mid n\ge 1\}$. This is a classic GATE problem. The strategy is to use the stack as a counter.

1. Phase 1: Read 'a's. While we are in the 'a' portion of the string, for every 'a' we read, we push a symbol onto the stack. Let's use the 'a' itself as the stack symbol. We'll stay in an initial state, say $q_0$, during this phase.
2. Phase 2: Switch to 'b's. When we read the first 'b', we know the 'a's have ended. This is the crucial switch. We pop one 'a' from the stack and move to a new state, $q_1$.
3. Phase 3: Read 'b's. Now in state $q_1$, for every subsequent 'b' we read, we must pop one 'a' from the stack.
4. Acceptance. If we finish reading the input string exactly when the stack becomes empty (except for our initial stack marker $Z_0$), it means the number of 'a's matched the number of 'b's. We can then move to a final state, $q_f$.

Let's formalize the transitions. We use the notation input, pop -> push.

• Start in state $q_0$ with $Z_0$ on the stack.

1. $\delta (q_0,a,Z_0)=\{(q_0,a{Z}_0)\}$ : Read the first 'a', push 'a' onto the stack.
2. $\delta (q_0,a,a)=\{(q_0,aa)\}$ : Read subsequent 'a's, push an 'a' for each.
3. $\delta (q_0,b,a)=\{(q_1,ϵ)\}$ : Read the first 'b', pop an 'a', and switch to state $q_1$.
4. $\delta (q_1,b,a)=\{(q_1,ϵ)\}$ : Read subsequent 'b's, pop an 'a' for each.
5. $\delta (q_1,ϵ,Z_0)=\{(q_f,Z_0)\}$ : After input is exhausted, if we see the bottom-of-stack marker, move to the final state $q_f$.

Any other input or stack combination would lead to a "crash" (no defined transition), meaning the string is rejected. For example, if we see another 'a' after a 'b', or run out of 'a's on the stack while still having 'b's to read, the machine halts and rejects.

This "push-then-pop" strategy is a fundamental pattern for designing PDAs for many related languages, such as balanced parentheses or palindromes.

The General Conversion: From CFG to PDA

While intuitive design is great for many GATE problems, there is a powerful, algorithmic way to convert any Context-Free Grammar into a PDA that accepts the same language. This proves the equivalence between CFGs and PDAs and gives you a surefire method for more complex languages.

The core idea is to make the PDA simulate a leftmost derivation of an input string. The stack will hold the sequence of variables and terminals that still need to be processed to complete the derivation.

The algorithm works as follows:

1. Initialization: The PDA starts in a q_start state. It immediately pushes a special bottom-of-stack marker (let's use '$') and then the grammar's start symbol $S$ onto the stack, and moves to a central q_loop state. The stack now contains $S\$$.

2. The Loop State (q_loop): This state does all the work. It checks the top of the stack and takes one of two actions:

   • If the top is a Variable (e.g., A): The PDA non-deterministically chooses one of the production rules for $A$, say $A\to \alpha$. It pops $A$ from the stack and pushes $\alpha$ onto the stack. Crucially, $\alpha$ is pushed in reverse order. For example, if the rule is $A\to XYZ$, the PDA pushes Z, then Y, then X. This ensures X is now at the top of the stack, correctly continuing the leftmost derivation. This is an $ϵ$-transition (it consumes no input).
   • If the top is a Terminal (e.g., a): The PDA must match this terminal with the current symbol in the input string. It reads the input symbol, and if they match, it pops the terminal from the stack. If they don't match, that path of computation fails.

3. Termination: If the PDA reaches a point where the top of the stack is the bottom-marker '$', it means the simulated derivation has perfectly matched the entire input string. The PDA can then make an $ϵ$-transition to pop the '$' and move to a final state, q_final.

Let's apply this to our grammar from the last lesson, $S\to aSb\mid ϵ$.

• Initialization: Start, push $, push S. Stack: S$. Move to q_loop.
• In q_loop:
  • Top is S. Two non-deterministic choices:
    1. Apply $S\to aSb$. Pop S, push b, push S, push a. Stack is now aSb$.
    2. Apply $S\to ϵ$. Pop S. Stack is now $.
  • Top is a. Read 'a' from input, pop a.
  • Top is b. Read 'b' from input, pop b.
  • Top is $. Pop $, move to q_final and accept.

By following these transitions, the PDA can successfully parse any string in $\{a^n{b}^n\}$ and will fail on any string not in the language.

Conclusion

Today, we built the automaton counterpart to the context-free grammar. We saw that a Pushdown Automaton, an NFA with a stack, has the right mechanism to recognize context-free languages.

Key Takeaways:

• A PDA uses its stack for memory, primarily to count or match nested structures.
• Transitions in a PDA depend on the current state, input symbol, and the symbol at the top of the stack.
• You can design a PDA intuitively for many common languages by defining phases of operation (e.g., push for 'a's, pop for 'b's). This is a critical skill for GATE.
• There exists a general algorithm to convert any CFG into an equivalent PDA, which proves their computational equivalence. This PDA simulates a leftmost derivation on its stack.

In the last two lessons, we've defined a class of languages (CFLs), a grammar to generate them (CFGs), and a machine to recognize them (PDAs). This completes a major tier in the Chomsky Hierarchy. However, even these powerful machines have their limits. In our next lesson, we will introduce the Pumping Lemma for Context-Free Languages, a tool that allows us to prove that certain languages, like $\{a^n{b}^n{c}^n\}$, are not context-free and thus cannot be recognized by any PDA.