Understanding how to convert a PDA to a CFG

Question

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions:

(current state, stack head, input character, replacement for old stack head, new state)

• $q_a,\#,\epsilon,\epsilon,q_a$
• $q_a,\#,a,|,q_a$
• $q_a,|,a,||,q_a$
• $q_a,|,b,\epsilon,q_b$
• $q_a,|,c,\epsilon,q_c$
• $q_a,|,b,\epsilon,q_b$
• $q_a,|,c,\epsilon,q_c$
• $q_a,|,c,\epsilon,q_c$

I'm trying to understand how the following equivalent grammar was produced (starting state $X_0$):

• $X_0 → (q_a,\#,q')$
• $(q_a,\#,q_a) → \epsilon$
• $(q_a,|,q_b) → b$
• $(q_a,|,q_c) → c$
• $(q_b,|,q_b) → b$
• $(q_b,|,q_c) → c$
• $(q_c,|,q_c) → c$
• $(q_a,\#,q') → a(q_a,|,q')$
• $(q_a,|,q'') → a(q_a,|,q')(q',|,q'')$

I don't understand the meaning of $q'$. I'm assuming it to be some kind of wildcard, cause many of the states wouldn't be accessible if it wasn't. Hopefully someone can recognize how this works.

P.S. epsilon means "nothing".

P.P.S the book I'm using is here (german), and the proof and algorithm is in 4.1.5, but I don't see how it could produce this.

Answer 1

The standard construction to obtain a CFG for a given PDA uses triplets, new symbols of the form $(p,A,q)$ where $p,q$ are states and $A$ is a stack symbol. These symbols are the nonterminals for the CFG. Intuitively, their meaning is the existence of a computation of the original PDA starting in state $p$ ending is state $q$ and removing a symbol $A$ form the stack.

If the PDA has an instruction $(p,A,a,BC,q)$ the PDA changes state, and replaces $A$ on the stack by $BC$. Now, if a computation that was supposed to remove $A$ from the stack, uses this instruction, it now has $BC$ on the stack instead, so we have to remove both symbols, in two consecutive computations. This is a kind of recursive thinking. For the CFG we get the set of productions $(p,A,q'') \to (q,B,q')(q',C,q'')$ for all possible states $q',q''$.

That is your answer, as you expected, $q',q''$ must take all possible values in $q_a,q_b,q_c$ so this single instruction gives 9 possible productions. Not all of them have to be of use, however.