$L=\{w|w\in\{0,1\}^*\wedge \#_1(w)=\#_2(w)\}$, where $\#_a(w)$ denotes number of symbol $a$ in word $w$. Check if $L^2$ is regular.

So idea is: $L^2 \cap 0^*1^*0^*=\{0^n1^{2n}0^n|n\ge 0 \}\notin Reg$
The fact that intersection is not regular is easy to show using pumping lemma. So due to the fact that regular languages are closer under intersection and $0^*1^*0^*$ is regular we conclude that $L^2$ is irregular.

What about this solution ?

  • 1
    $\begingroup$ If $L^2=\{ww:w\in L\}$, then this is almost right: you need $n\ge 0$, not $n>0$, in the description of $L^2\cap 0^*1^*0^*$. $\endgroup$ – Brian M. Scott May 5 '15 at 22:13
  • $\begingroup$ yes, you are right. I corrected it. $\endgroup$ – user220688 May 6 '15 at 17:27
  • 1
    $\begingroup$ Looks fine now. $\endgroup$ – Brian M. Scott May 6 '15 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.