# 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?

• 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