Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
$\{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

1 Answer 1

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
share|improve this answer
    
(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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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