3
$\begingroup$

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

I have the following PDA. alt text

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
    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. – 2011-01-16

1 Answers 1

4

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.
enter image description here

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:
enter image description here

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: enter image description here

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: enter image description here

Reconstruct the last transition rule \epsilon, S \rightarrow aTXb$, we have our final PDA as follows: enter image description here

Reference

  • Introduction to the Theory of Computation by Micheal Sipser
  • Lecture notes from prof. Marvin K. Nakayama, New Jersey Institute of Technology
  • 0
    (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. – 2012-10-23