Converting a pushdown automaton (that accepts by final state) to a context-free grammar

643 Views Asked by At

Given the following PDA:

$$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$

where the transition function $\delta$ is given by:

$$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, X) = \{(q, XX)\} \\ \delta(q, 1, X) = \{(q, X)\} \\ \delta(q, \epsilon, X) = \{(p, \epsilon)\} \\ \delta(p, \epsilon, X) = \{(p, \epsilon)\} \\ \delta(p, 1, X) = \{(p, XX)\} \\ \delta(p, 1, Z_0) = \{(p, \epsilon)\} \\ $$

I want to convert the PDA $P$ to a context-free grammar.

Now I know that the standard way of doing this is to first convert the PDA $P$ that accepts (a language $L$) by final state to a PDA $P_N$ that accepts the same language $L$ by empty stack. Once $P_N$ is known, converting it to a context-free grammar is a pretty straightforward and mechanical process.

That said, in this case it would be a lot of work since the number of states in $P_N$ would increase to four (from two in $P$), and $P_N$ would have more rules in its transition function $\delta_N$. If possible, I would like to avoid doing all of that work, even if it is a guaranteed solution.

I decided instead to inspect the PDA $P$ and see if I could determine the language $L$ that it accepts. The conclusion that I came to is that the language accepted is regular, and can be expressed by the following regular expression:

$$ 0(0 + 1)^* $$

And then converting from a regular expression to a context-free grammar is not too bad:

$$ S \rightarrow 0A \\ A \rightarrow BA \mid \epsilon \\ B \rightarrow 0 \mid 1 $$

Sorry for the long-winded introduction. My question is, is my answer right? Am I correct in my assumption that the language $L$ accepted by $P$ is regular, and can be expressed by $0(0 + 1)^*$?