Context-free languages closure property

245 Views Asked by At

Trying to rove that the set of all context-free languages over a language Σ is closed under TRIPLE where TRIPLE (L1, L2, L3) = L1L2L3. Pretty much, TRIPLE, applied to three languages yield the concatnation of the three languages in order.

I am a little confused on where to start but my initial approach was to construct a grammar for the union of the set off all context-free languages and TRIPLE by taking all the rules from both grammars. But I am not sure how to go about this or if this is the right approach. Any help is appreciated.

1

There are 1 best solutions below

2
On

HINT: First show that the concatenation of two context-free languages is context-free; then you can prove by induction on $n$ that the concatenation of $n$ context-free languages is context-free, and the case $n=3$ gives you the desired result.

Suppose that $L_1$ and $L_2$ are context-free languages. They are generated by context-free grammars $G_1$ and $G_2$, respectively with initial symbols $S_1$ and $S_2$, say. Try to build a context-free grammar from $G_1$ and $G_2$ with a new initial symbol $S$ and a production $S\to S_1S_2$ in such a way that it generates $L_1L_2$; it’s pretty straightforward once you have this basic idea.