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,


      ▲                         |  

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?

  • $\begingroup$ Please try to write down all the details of the DFA by yourself before posting anywhere. $\endgroup$ – Abuzer Yakaryilmaz Jan 26 '13 at 18:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Karolis Juodelė Jan 26 '13 at 19:38
  • 3
    $\begingroup$ The language $\Sigma^*$ is regular, so how come there are non-regular languages? They are all subsets of $\Sigma^*$. $\endgroup$ – Yuval Filmus Jan 27 '13 at 0:56
  • $\begingroup$ I am not asking subsets. @Yuval $\endgroup$ – henry Jan 27 '13 at 4:01
  • $\begingroup$ Then what are you asking? $\endgroup$ – Raphael Jan 28 '13 at 10:13

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 27 '13 at 0:55
  • 1
    $\begingroup$ You're right, Ran. The key difference between the two language is the first one doesn't need to remember its contents just to calculate the length is enough, while the second language need to analyse whether w and w are identical. Get your point. Thanks. :-) $\endgroup$ – henry Jan 27 '13 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.