Examples of Converting PDA to CFG (General Case)

Let’s start by looking at a few examples of converting an arbitrary PDA to CFG.

First example

The following PDA accepts the language $L_n = \{a^nb^n \;|\; n\geq 0\}$.

To convert this PDA to a CFG, we first normalize it by adding the transition $a,X\to XX$ on state $q_0$.

There are two accepting states, so the first boilerplate rules are:

As usual, we have nullity rules for each state:

With multiple states, we must entertain all possible combinations of states as we convert each transition to grammar rules. This is where things get tedious. Consider the first transition: $a,\lambda\to X$. We begin to extract a grammar rule for this transition as follows:

We have not yet populated the third slot (marked by a dash) of each grammar variable. There are examples with only one state to consider, but now there are two states. Recall that the interpretation of the incomplete rule above is, “Starting in state $q_0$, we pop nothing, consume $a$, push $X$, and move in one step to state $q_0$.” Where we eventually end up after multiple moves is reflected in the third slot of each variable, and by the definition of the notation $\langle pVq\rangle$, those slots must represent the same state—consuming $a$, pushing $X$, and staying in $q_0$ is just the first step in that journey. Since we must consider all possibilities of target states, we form two rules, one for each state in the machine:

Remember: The state in the third slot in the variable on the left of each line must be identical to the third slot of the last variable on the right.

Now consider the rule $a,X\to XX$. This time there will be two variables on the right-hand side of the rule. We begin with the following incomplete rule pattern:

The identical patterns above indicate that the states in those positions must be the same. The single-dash pattern was explained above—it represents where we end up when the aftereffects of popping $X$ have vanished from the stack. Part of those aftereffects is that two additional $X$'s are pushed and must be subsequently processed. The box patterns must be identical because the state we end up in after processing the first of the two additional $X$'s is where we must continue from to process the second $X$. Therefore, we have four possible grammar rules for this transition:

One of those rules, set off in a different typeface, has an invalid variable: $\langle \mathsf{q_1Xq_0}\rangle$. It is not possible to move from state $q_1$ to state $q_0$ in this PDA, so we remove this rule from further consideration, leaving only three possible rules for the associated transition.

In a similar fashion, the transition $b,X\to\lambda$ from $q_0$ to $q_1$ yields the following possibilities, one of which we immediately discard because it also reflects an invalid path in the PDA:

Finally, the transition $b,X\to\lambda$ on $q_1$ ...