Problem Detail: I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG? For example: to write CFG for the automata 
My attempt: $S=A_{03}$ because $q_{color{blue}0}$ is the initial state and $q_{color{blue}3}$ is the final state. There are $4$ states so we will have $4^2$ variables: $$A_{00},A_{01},A_{02},A_{03}, A_{10},A_{11},A_{12},A_{13}, A_{20},A_{21},A_{22},A_{23}, A_{30},A_{31},A_{32},A_{33}$$ for each state $q_{i}$ of the automata $A_{ii}tovarepsilon$ $$A_{00}to varepsilon A_{11}to varepsilon A_{22}to varepsilon A_{33}to varepsilon$$ For each triplet of states $q_i,q_j,q_k$, we add the rule $A_{ij}to A_{ik}A_{jk}$, this gives us $4^3=64$ rules: $$A_{00}to A_{00}A_{00}|A_{01}A_{10}|A_{02}A_{20}|A_{03}A_{30} A_{01}to A_{00}A_{01}|A_{01}A_{11}|A_{02}A_{21}|A_{03}A_{31} A_{02}to A_{00}A_{02}|A_{01}A_{12}|A_{02}A_{22}|A_{03}A_{32} bullet bullet bullet A_{33}to A_{30}A_{03}|A_{31}A_{13}|A_{32}A_{23}|A_{33}A_{33}$$ I am stuck here
My attempt: $S=A_{03}$ because $q_{color{blue}0}$ is the initial state and $q_{color{blue}3}$ is the final state. There are $4$ states so we will have $4^2$ variables: $$A_{00},A_{01},A_{02},A_{03}, A_{10},A_{11},A_{12},A_{13}, A_{20},A_{21},A_{22},A_{23}, A_{30},A_{31},A_{32},A_{33}$$ for each state $q_{i}$ of the automata $A_{ii}tovarepsilon$ $$A_{00}to varepsilon A_{11}to varepsilon A_{22}to varepsilon A_{33}to varepsilon$$ For each triplet of states $q_i,q_j,q_k$, we add the rule $A_{ij}to A_{ik}A_{jk}$, this gives us $4^3=64$ rules: $$A_{00}to A_{00}A_{00}|A_{01}A_{10}|A_{02}A_{20}|A_{03}A_{30} A_{01}to A_{00}A_{01}|A_{01}A_{11}|A_{02}A_{21}|A_{03}A_{31} A_{02}to A_{00}A_{02}|A_{01}A_{12}|A_{02}A_{22}|A_{03}A_{32} bullet bullet bullet A_{33}to A_{30}A_{03}|A_{31}A_{13}|A_{32}A_{23}|A_{33}A_{33}$$ I am stuck here
Asked By : Nehorai
Answered By : vonbrand
There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals. Added, as requested by Nehorai: Take a PDA $M = (Q, Sigma, Gamma, delta, q_0, Z_0, varnothing)$ that accepts $L = mathcal{N}(M)$ by empty stack (if you have a PDA accepting by final state, first convert to empty stack). We define a CFG that accepts $L$. The nonterminals are symbols of the form $[p, A, q]$ with $p, q in Q$, $A in Gamma$, and a start symbol $S$. The idea is that if $[p, A, q] Rightarrow^* sigma$, then if $M$ starts in state $p$ with $A$ on its stack, after consuming $sigma$ it might be in state $q$ and the stack is shorter by one symbol for the first time. Consider an $A$ on the (eventually empty) stack as commitment to get rid of it. If there is a move $(p, A_1 A_2 dots A_n) in delta(q, x, A)$ with $x = epsilon$ or $x in Sigma$, this adds productions: $begin{align} [q, A, q_n] rightarrow x [p A_1 q_1] [q_1 A_2 q_2] dots [q_{n – 1} A_n q_n] end{align}$ I.e., we consume $x$ from the input (generate it in the grammar), going to state $p$, from which we now are committed to get rid of $A_1 dots A_N$. We don’t know what states $q_1, dotsc, q_n$ are involved, we just know that after consuming e.g. $A_i$ we will be in some state $q_i$, from which we have to consume $A_{i + 1}$. So we will have to consider all possible collections of states for them. In the special case $(p, epsilon) in delta(q, x, A)$, the above simplifies to: $begin{align} [q, A, p] rightarrow x end{align}$ If $x = epsilon$, the above formally doesn’t give a context free grammar, but with the standard construction $epsilon$ productions can be eliminated. To start the ball rolling, the stack initially contains just $Z_0$, we are in state $q_0$, and end up in any state: $begin{align} S rightarrow [q_0, Z_0, q] end{align}$ for any state $q in Q$. This should convince you the above construction is correct. It is far from a proof…
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/51658
