# Context free grammar as minimal solution of a system of equations

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.

• 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. – Rick Decker May 17 '16 at 14:57
• 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. – Raphael May 17 '16 at 16:29
• The productions of the context-free grammar directly give you the set of equations. – Yuval Filmus May 17 '16 at 16:38