1

I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be concatenated, but I have some doubts on determining the category the result belongs to. Maybe troughout an example it will be easier to solve all my doubts and let you understand better the nature of my question. For instance, let $L = \left \{ 0^{n}\cdot 1^{n} \mid n \geq 0 \right \}$ and $L^{R} = \left \{ 1^{n}\cdot 0^{n} \mid n \geq 0 \right \}$

Those two languages are obviosly not regular (it's easy to apply the Pumping Lemma here) but what happens if I define this result language $L{}' = L \cdot \left \{ 0, 1 \right \}^{*} \cdot L^{R}$

I think it should be still not regular, since we can apply again the pumping lemma by letting be $p$ the length of the pumping and $w=0^{p}1^{2p}0^{p}$, w is in $L'$. The contination is easily.

But is it good to consider that w of $L'$?

Raphael
  • 72,336
  • 29
  • 179
  • 389
gr1ph00n
  • 21
  • 3
  • See the related question http://cs.stackexchange.com/questions/13956/why-is-this-language-involving-reversal-regular – J.-E. Pin Sep 06 '13 at 09:07

1 Answers1

1

The language $L'$ contains all possible strings, and so it is in particular regular. This is because the empty word is in $L$, and so $L\cdot \{0,1\}^* \cdot L^R$ contains $\{0,1\}^*$. If you "proved" that it's not regular using the pumping lemma, you have made a mistake applying it. Try to find it; this will lead to better understanding of the pumping lemma.

Yuval Filmus
  • 276,994
  • 27
  • 311
  • 503
  • I did a mistake because I did a wrong concatenation of the languages, I did exactly the opposite of what You suggested. I took the empty word in {0,1}, so that I considered $L \cdot L{}'$. In this way I did not consider that L' contains $\left { {0,1}\right }^{}$ – gr1ph00n Sep 05 '13 at 13:51