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.

  • 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}$.2011-01-16
  • 0
    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.2011-01-16
  • 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