It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example:

$$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X &=\{{a}\}Y \{{v}\} \end{align*}$$

generates the language $\{a^nb^n : n \in \mathbb{N}\}$.

How can I prove that fact? How do I make the step from equations over sets to context-free grammars? In contrast to regular languages, which are accepted by automata without stack, it seems like the equations that generate CFG can't be easily transformed to pushdown automata.

  • 1
    $\begingroup$ You might want to expand your question by providing a bit more context. Do you want to include operators other than union and concatenation? For the benefit of a larger audience, you might also want to define what a minimal solution to a system of language equations is. I'm voting to reopen this question, but if that doesn't work, you might consider asking this in Theoretical Computer Science, where it might get a friendlier reception. $\endgroup$ – Rick Decker May 17 '16 at 14:57
  • $\begingroup$ Check out the work by Schützenberger and/or Kuich. Or any textbook that shows that CFGs and PDAs define the same class of languages. $\endgroup$ – Raphael May 17 '16 at 16:29
  • $\begingroup$ The productions of the context-free grammar directly give you the set of equations. $\endgroup$ – Yuval Filmus May 17 '16 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.