In our lecture our professor claimed this result:

Let $\{1,\dots,k\}$ be an alphabet (or terminals) for the context free grammar $\tau$, $L(\tau)$ is the language generated by $\tau$. Let $G_1,\dots, G_k$ be context free languages. For $\alpha=n_1\dots n_m \in L(\tau)$, let $\phi : L(\tau)\to \{L \mid L\ is\ a\ language\}$ be the function such that $\phi(\alpha)=G_{n_1}\dots G_{n_m}$ then $\forall \alpha, \ \phi (\alpha)$ is a context free language

The problem is that in my mind concatenation is enough to lead to the same result as above, so it seems to me a bit pointless and unuseful theorem: where am I wrong?


Concatenation is indeed enough to prove this result. However, this result may just be useful in a larger proof of something else where you want to directly use this and not go through this proof inside the proof using concatenation. In other words it may not be useful on its own but useful to clarify some proofs.

Also, $\bigcup_{\alpha\in L(\tau)}\phi(\alpha)$ is a context free language. This is a (may be) more useful result. Are you sure you get it right?

[EDIT] :

To prove this, consider (without loss of generality) that all the non-terminal of $\tau,G_1,\dots,G_k$ are different. We denote $S_i$ the initial non terminal of grammar $G_i$ and consider the grammar $\tau'$ composed of all the rules of $G_1,\dots,G_k$ and the rules of $\tau$ in which, each time a terminal $t$ appear it substituted by $S_t$.

It is easy to show that $L(\tau')=\bigcup_{\alpha\in L(\tau)}\phi(\alpha)$

  • $\begingroup$ Can you explain your claim please? It's indeed useful, but can't see why is true. $\endgroup$ – Davide F. Feb 24 '15 at 11:44
  • $\begingroup$ @DavideF. I edited the answer to add a sketch of proof. I hope it help. $\endgroup$ – wece Feb 24 '15 at 11:52

Your Answer

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

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