Concatenation of context free language and a maybe pointless theorem

243 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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)$