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

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