1
$\begingroup$

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'$?

$\endgroup$
1
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 \}^{*}$ $\endgroup$
    – gr1ph00n
    Sep 5 '13 at 13:51

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.