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 winSigma^*}$ 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
