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

Question

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?

Answer 1

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.

Answer 2

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}