Converting PDA to CFG

Question

I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\ \Gamma$ for $[pXq]$ we have include the sequence of derivations which would pop X from the stack.

I partially understand what is going on but I cannot seem to understand how do I unroll the productions to form strings so I can understand it clearly. Take the production (5) in the example for instance. From what I understand it we are in state p we want to pop A and in the end we should be in state p with empty stack. As we are reading 0 we have zero in the production followed by $[pAq][qAp]$, this is the thing which I am not understanding because if we look at the PDA there is no way of going to q on reading 0. I would like to know what really is going on.

A related question is answered here but I cannot understand it how to clear my confusion.

Answer 1

You have the basic intuition right. The variable $[p,A,q]$ represents the set of (strings accepted by) computations from state $p$ to state $q$ that will pop the topmost symbol $A$ from the stack.

Technicaly the relation between grammar $G$ and pda $M$ is given on the top of the slide you show.

Then the construction follows recursion. If the pda pops $A$ but pushes $B_1B_2B3$ the grammar will replace the computation on $A$ starting in $p$ and ending in $q$ into three separate computations $[q_1,B_1,q_2][q_2,B_1,q_3][q_3,B_1,q]$. Here the intermediate states $q_2,q_3$ are unknown and are guessed by the grammar. Only $q_1$ is known, as it is the state where the pda instruction moves to.

Your observation is right. This standard construction might introduce triplets $[p,A,q]$ that will be useless. In your example there will be no computations from $q$ to $p$ so a triplet $[q,A,p]$ is never used in a succesful derivation. That is not problamatic. The construction just produces all possibilities, and variables that turn out to be useless can be removed afterwards if one really wants.

Note. The other question you link to uses a different Sipser style automaton model! There stack symbols are pushed one by one without popping at the same time. To add to the confusion the answer given at that question perfectly matches the construction from your slide!