[Solved]: Without using pumping lemma, can we determine if $A ={ww mid w in {0,1}^* }$ is non regular?

ignougroup
Problem Detail: Without using pumping lemma, can we prove $A ={ww mid w in {0,1}^* }$ is non regular? Is $L= {w mid w in {0,1}^* }$ non regular? I’m thinking of using concatenation to prove the former isn’t regular. If L is non regular then so is LL

Asked By : Iancovici

Answered By : Shaull

Your idea (while interesting) is unlikely to work for two reasons:

  1. How would you express $A$ as a concatenation of a language with itself?
  2. If $L$ is non-regular, it may still be the case that $LL$ is regular. See this post: Is $A$ regular if $A^{2}$ is regular?

You could prove it using the Myhill-Nerode theorem – show that there are infinitely many equivalence classes. Or you could simply use a pumping argument without the lemma. That is, follow the proof of the lemma for this particular language.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11759