Show that a language is not regular using Myhill-Nerode Theorem

1.4k Views Asked by At

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that?

Let Σ = {0, 1}. 
Let L = {ww|w ∈ Σ*}

I am not sure where or how to go about this...

1

There are 1 best solutions below

0
On BEST ANSWER

HINT: I use the notation and terminology of the Wikipedia article on the Myhill-Nerode theorem. Show that for this language $L$, the equivalence relation $R_L$ has infinitely many equivalence classes. Use the fact that if $u,v\in L$, $u\ne v$, and $|u|=|v|$, then $uu\in L$, but $vu\notin L$, so $u$ is a distinguishing extension for $u$ and $v$.