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...
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...
Copyright © 2021 JogjaFile Inc.
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$.