2
$\begingroup$

I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two. He splits the proof (Lemma 2.27, page 121) in 4 parts:

  1. Modify the PDA so there's 1 start state, 1 final state and every transition increments or decrements the stack height by one. This part is straightforward.
  2. Generating rules.
  3. Proving: If Apq generates x, then x can bring P from p with empty stack to q with empty stack.
  4. Proving: If x can bring P from p with empty stack to q with empty stack, Apq generates x

First, I don't understand what the rules accomplish. Then I don't understand how the last 2 proofs show that PDA can be converted to CFG. I watched youtube lectures (including EasyTheory's), the diagrams in the book and some notes online but failed to gain the intuition for what's happening in the proof. I would appreciate if someone could demystify it for me.

$\endgroup$

2 Answers 2

1
$\begingroup$

The secret of the PDA to CFG proof is recursion. CFG's are by definition good in recursion.

Sipser explicitly constructs a CGF and the Lemma's are provided to show his construction works. His CFG has nonterminals of the form $A_{pq}$ and the intuitive meaning is that they correspond to "computations of the PDA starting in state $p$ ending in state $q$ where at the start and at the end the stack is empty". The proof shows that the CFG generates strings on nonterminal $A_{pq}$ when the PDA reads the same strings on computations of the $A_{pq}$ type.

Here are the productions that should make this work.

(1) Choose any two matching instructions as follows. One instruction from state $p$ to state $r$ which pushes a stack symbol $u$ and reading $a$ from input, and one from state $s$ to state $q$ popping same $u$ reading $b$. Then $A_{pq} \to a A_{rs} b$.

Any computation of a PDA that pushes $u$ must later pop that symbol where the stack below has not been touched. That is recursion: the computation $A_{pq}$ is replaced by the computation $A_{rs}$ which is inside the original computation, but has now additional $u$ on stack, from state $r$. We compute until $u$ is popped, and this is possible in state $s$.
This is for specific $p,q,r,s$ that have matching push and pop instructions.

(2) The computation from $p$ to $q$ from empty stack to empty stack might have an empty stack on the way. Then we have to introduce an intermediate state $r$, more or less in order to continue from there. (We push and pop our first stack symbol, and now need to continue with the next stack symbol.) Thus $A_{pq}\to A_{pr}A_{rs}$. This is for all $p,q,r$ in order to continue a computation.

(3) The empty computation is also of the right form, so we have $A_{pp} \to \varepsilon$ as it generates nothing.

I like to note that Sipser has a somewhat nonstandard proof. Most books have a similar recursive construction, but also include the nonterminal that is put on the stack. Hence its nonterminals are of the form $[p,u,q]$ meaning a computation from state $p$ to state $q$ with only $u$ on the stack until that $u$ is popped. Same intuition, technically different as Sipser "predicts" the final $q$ (it is chosen as a "pop" to match the initial "push") whereas many other books "guess" the state $q$ where the pop will occur.

$\endgroup$
4
  • $\begingroup$ Could you elaborate on this bit: "This is for all 𝑝,𝑞,𝑟 in order to continue a computation." ? I feel like it should only be on those states where (p,r) has empty stack and (r,q) has empty stack. By (p,r) I mean that p starts in an empty stack and r ends with an empty stack. $\endgroup$
    – learner
    Aug 22, 2022 at 19:22
  • $\begingroup$ Secondly, is there an error in this line of the proof: "For each pair of states p and q in P, the grammar will have a variable Apq. This variable generates all the strings that can take P from p with an empty stack to q with an empty stack" I feel that it should be "same stack height" instead of "empty stack" as in the case of Ars of rule 2 $\endgroup$
    – learner
    Aug 22, 2022 at 19:44
  • $\begingroup$ The "empty stack" is on purpose. In principle "same stack height" would also work, but then one should add that the lower stack symbols are not touched. Since we do not consider these lower stack symbols, we can ignore them and just consider the stack empty. When the computation works on empty stack, then it works on any stack (and symbols below are not seen by the PDA). (Note: Sipser has fiddled with the definition of PDA. The generic definition does not allow computation on empty stack: a PDA will always pop exactly one stack symbol and push any number. Anyway, the notions are equivalent.) $\endgroup$ Aug 22, 2022 at 20:33
  • $\begingroup$ We agree on the $p,q,r$ case. Those productions are only used where the $(p,r)$ and $(r,q)$ computations start and end on empty stack, but they are available for every combination, just in case such a computation exists. In general a $A_{p,q}$ might not exist (for example, there is no instruction that pops and ends in $q$) and in that case the symbol will be present in the grammar, but will be useless, it does not generate terminal strings. $\endgroup$ Aug 22, 2022 at 20:39
0
$\begingroup$

Let's denote the start state as $s$ and accept state as $t$. To prove that every PDA $P$ can be converted to some CFG, we can:

  1. for every PDA $P$ show an CFG $A$. This is part 2: show how to construct the CFG $A_{st}$.
  2. prove that the languages recognized by $P$ and $A$ are equivalent.

To prove the second point, we should show it in both directions:

  1. $L(P) \subseteq L(A)$ (here $L(P)$ means the language recognized by $P$). Here is the goal of part 4: every string recognized by $P$, (i.e. can bring $P$ from $s$ with empty stack to $t$ with empty stack), can also be generated by $A_{st}$.
  2. $L(A) \subseteq L(P)$. This is the goal of part 3: every string generated by $A_{st}$ can bring $P$ from $s$ with empty stack to $t$ with empty stack, i.e. be recognized by $P$.

Sipser proved the two points above inductively, so part 3/4 are more generalized version of the two goal above.

In fact, the final proof is often presented in the "opposite" direction of our thinking (i.e., the part of the proof that we end up thinking about may appear at the very beginning of the proof, while the most intuitive part is often hidden), so to catch the intuition is always difficult somehow.

$\endgroup$
4
  • $\begingroup$ Why is the second rule in generating the grammar G for each p,q,r but the first one only for some p,q? $\endgroup$
    – learner
    Aug 22, 2022 at 13:46
  • $\begingroup$ Secondly, is there an error in this line of the proof: "For each pair of states p and q in P, the grammar will have a variable Apq. This variable generates all the strings that can take P from p with an empty stack to q with an empty stack" I feel that it should be "same stack height" instead of "empty stack" as in the case of Ars of rule 2 $\endgroup$
    – learner
    Aug 22, 2022 at 19:44
  • $\begingroup$ First, I think rule 1 (in Sipser's) is like "forall p, q, for some r, s" but not "for some p, q, r". More precisely, it's "forall (p, r), (s, q) that (p, r) pushes the same state as the one (s, q) pops". This is crucial since the grammar (without this restriction) will generate a string that pops a state which is not on the top of the stack. $\endgroup$
    – Marcythm
    Aug 23, 2022 at 4:04
  • $\begingroup$ For your second question, here I assume what you mean is "same stack height is better" (but not "empty stack is not enough to prove"). 1. it's obvious that the condition of "same stack height" is a superset of "empty stack", 2. in the condition of "same stack height" (but not included in "empty stack"), there will be some p, q that x bring P from p to q, s.t. it pops a state at p and pushes a state when reaching q. But notice, here the state popped at p and the one pushed at q can be different, which maybe cannot generated by Apq. $\endgroup$
    – Marcythm
    Aug 23, 2022 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.