[Solved]: How come {ww} isn't regular when {uv | |u|=|v|} is?

Problem Detail: 

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?

Asked By : henry

Answered By : Ran G.

well, there are things that a DFA can do, and things that DFA cannot do. A DFA is quite a simple machine, and it has no access to "memory". The only "memory" it has is its current state, i.e., a very limited memory. A DFA can do tasks that require finite amount of memory, but nothing more than that.

To check if the input is of even length - is very simple task. It requires only 1 bit of memory (odd/even). therefore, it can be done by a DFA.

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.

at least, this is the intuitive explanation.

Best Answer from StackOverflow

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