# Converting PDA to CFG

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.

• Source: the slide you show is from a deck produced by Marta Vomlelová, on Automata and Grammars- TIN071. – Hendrik Jan Aug 4 '20 at 19:58
• I wanted to share link but I cannot for English only Czech slides are public – lemniscate Aug 5 '20 at 19:09

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.