1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you already proved that the concatenation of two context-free languages is context-free? $\endgroup$ – Brian M. Scott Apr 29 '15 at 19:50
  • 1
    $\begingroup$ No I have not proven that yet. Could you give me a direction on how to prove it? I am a little ew to CFG and CFLs $\endgroup$ – Raj Apr 29 '15 at 20:51
  • $\begingroup$ Okay; I’ve written an answer accordingly. $\endgroup$ – Brian M. Scott Apr 29 '15 at 20:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the help! I was able to figure out S - s1s2. Could you give me a little help on how to prove by induction for n = 3? Give me a some start. Thanks $\endgroup$ – Raj Apr 30 '15 at 22:14
  • 1
    $\begingroup$ @Raj: Note that $L_1\ldots L_{n+1}=(L_1\ldots L_n)L_{n+1}$, so it can be seen as the concatenation of two languages. And if you already know that $L_1\ldots L_n$ is context-free, then ... $\endgroup$ – Brian M. Scott Apr 30 '15 at 22:15

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.