# Pushdown Automata deriving context free language

I'm trying to understand how you derive a context free grammar (CFG) from a Pushdown Automata (PDA)?

I have the following PDA.

I believe the following context-free language can be derived..

{0^n1^n|n≥0}

My problem is I don't understand how you can build the context free grammar from a PDA and vice versa. How would I build a PDA from a CFG? I'd really appreciate if someone could walk me through this process.

-
$\{0^n1^n\mid n≥0\}$ isn't a context-free grammar, it's just a set (in “set-builder” or “set comprehension” notation). The CFG would be $A \rightarrow \epsilon \mid \text{0}A\text{1}$. – Kevin Reid Jan 16 '11 at 16:52
Thanks, fixed my mistake. – Ulkmun Jan 16 '11 at 16:58
This is probably homework (?) since this question is (read: should be) covered in every introductory course for TCS. Therefore, you can find the answer in every text book on the topic. – Raphael Jan 16 '11 at 17:59
It's not homework. I'm studying for an exam and trying to understand what's happening here. I've been reading a text book (which this example is derived from) and I've had no luck. – Ulkmun Jan 16 '11 at 18:06

To construct a PDA from CFG, we only need to use these two simple rules:

1. If the rule is of the form $S \rightarrow t$, where $t$ is a terminal, the transition is $t, t \rightarrow \epsilon$.
2. If the rule is of the form $S \rightarrow s$, where $s$ is any string (including variables and terminals), $|s| > 1$, the transition is $\epsilon, S \rightarrow s$.

The first rule is simple and straightforward, but the second rule requires a little bit of work. Let says, we have a CFG defined as follows: $$S \rightarrow aTXb$$ $$T \rightarrow XTS | \epsilon$$ $$X \rightarrow a | b$$ Initially, we have three states, where S stands for starting rule and \$stands for stack symbol. Your book probably uses Z for stack symbol, so feel free to change it. It's just the matter of preference. The restriction of a stack in PDA is that we can only push "one" symbol at a time. So to push a production rule onto a stack, we will break them into variables and terminals. Specifically, have a look at above picture, you can see that the first transition rule says push$S\$$onto a stack, where \$$ is stack symbol. This is not allowed in PDA, so we have to break the transition into two steps:

Note that this transition is a little special because it involves both stack variable $\$$and the starting variable S. The next example of breaking long production rule should be more obvious. Firstly, all the production rule will go through the state after we pop S, i.e 2. We then apply the same procedure for any production rule that has length greater 1. So our first transition graph is as below: In this graph, here are three transitions that need to be reconstructed. They are:$$\epsilon, \epsilon \rightarrow S\\epsilon, S \rightarrow XTS\epsilon, S \rightarrow aTXb$$Since we've already done$\epsilon, \epsilon \rightarrow S$, the next transition need to reconstructed is$\epsilon, S \rightarrow aTXb$. Note that the order of popping is from "right to left". So we pop$S \rightarrow T \rightarrow X$respectively as below: Reconstruct the last transition rule$\epsilon, S \rightarrow aTXb\$, we have our final PDA as follows:

Reference

• Introduction to the Theory of Computation by Micheal Sipser
• Lecture notes from prof. Marvin K. Nakayama, New Jersey Institute of Technology
-
(1) That seems the other way around. The question is how to obtain a CFG given a PDA. Which is harder. (2) Many PDA models do allow to push several symbols in one move. I guess only Sipser made another choice. Beats me why. – Hendrik Jan Oct 23 '12 at 20:53