# 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 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 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 at 0:56
I am not asking subsets. @Yuval –  henry Jan 27 at 4:01
Then what are you asking? –  Raphael Jan 28 at 10:13

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

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

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.

-
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 at 0:55
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. :-) –  henry Jan 27 at 4:05

You are misinterpreting languages ww and language of DFA that is L1:

[Question]:

• L ={ ww| w = w} is a Regular Language(RL). Because we can get the DFA like below is possible.

DFA:  L1 ={ w1w2| |w1| = |w2|, where w1 , w2 ∈ {a, b}* }

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


[DOUBT]

What is L ={ ww | where w ∈ {a, b}* } is ?

L is even length string consist of a and b that is has some prefix sub string equal to suffix sub string. some example of L are { aa, bb, abab, aaaa, bbbb, abaaba, abbabb, .....}

Whats language of DFA or L1 ={ w1w2| |w1| = |w2|, where w1 , w2 ∈ {a, b}* } ?

All even length strings consist of a and b say L1 for example {ab, ba, aabb, baab, ab, aa, bb, ababa, baba, abbba, ...}

Note: all even length strings consist of a and b are not in L for example {ab, ba, aabb, baab, ab} but this string in DFA's language = L1.

so, L(DFA)=L1 != L

[DOUBT-1]

Relation between L and L(DFA)=L1 ?

As I wrote in note, L ⊆ L(DFA) so every string that belongs to L also element of language of DFA and accepted you DFA. (this is you confusion)

Also, language L ={ ww| |w| = |w| } is not Regular Language.And we can't draw DFA for this language. BOTH LANGUAGES ARE NOT SAME! (L != L1)

L is much restricted then L(DFA)

L= { WW|W } is not regular can be proof using pumping lemma

L also not even context free language, but context sensitive language

-
Because I made mistakes in my previous answer on SO, I am also updating here (its answer replicate of my own) –  Grijesh Chauhan Jan 27 at 4:41
So all you are saying here is that the two considered languages are not equal? I think the OP is well aware of that. –  Raphael Jan 28 at 10:14
@Raphael Yes this question I didn't answered well, I will update my answer ...although I given an hint that for W in L(DFA) we can have finite choice a or b –  Grijesh Chauhan Jan 28 at 12:16
@Raphael Ran G already given answer very well that's why I didn't update –  Grijesh Chauhan Jan 28 at 12:26