# How come {ww} isn't regular when {uv | |u|=|v|} is?

As we know, using the pumping lemma, we can easily prove the language $L = \{ w w \mid w \in \{a,b\}^* \}$ is not a regular language.

However, the language $L_1 = \{ w_1 w_2 \mid |w_1| = |w_2| \}$ is a regular language. Because we can get the DFA like below,

DFA:

--►((even))------a,b---------►(odd)
▲                         |
|--------a,b--------------|


My question is, $L = \{ w w \mid w \in \{a,b\}^* \}$ also has the even length of strings ($|w|=|w|$, definitely), so $L$ still can have some DFA like the one above. How come is it not a regular language?

-

## migrated from cstheory.stackexchange.comJan 26 '13 at 19:25

This question came from our site for theoretical computer scientists and researchers in related fields.

Please try to write down all the details of the DFA by yourself before posting anywhere. –  Abuzer Yakaryilmaz Jan 26 '13 at 18:38
You said you knew why $ww$ is not regular, so what are you asking about? Generally if for two languages, $L_1 \subset L_2$, this tells you nothing about the complexity of one, even if you know the other. –  Karolis Juodelė Jan 26 '13 at 19:38
The language $\Sigma^*$ is regular, so how come there are non-regular languages? They are all subsets of $\Sigma^*$. –  Yuval Filmus Jan 27 '13 at 0:56
I am not asking subsets. @Yuval –  henry Jan 27 '13 at 4:01
Then what are you asking? –  Raphael Jan 28 '13 at 10:13

However, for the second language $\{ ww \mid w\in\Sigma^*\}$ the DFA needs to check that the first $w$ is identical to the second $w$. How can you do that with no memory? In fact, since $w$ can be of any length, a (one-pass) machine that checks that the two copies of $w$ are the same must have infinite memory (to accommodate any $w$..). But a DFA has only limited memory, and thus cannot solve this task.
This can be made into a formal proof using the Myhill-Nerode relation. The language $\{ww\}$ has a different equivalence class for each word $w$, so a DFA accepting it must have infinitely many states. –  Yuval Filmus Jan 27 '13 at 0:55