I have to prove that the following languages are not regular using the Myhill-Nerode Theorem.
- $\{0^{n}1^{m}0^{n} \mid{} m,n \ge 0\}$
- $\{w \in\{0,1\}^{\ast}\mid w\text{ is not a palindrome}\}$
For the first question, I did the following:
I considered the set $\{0^n1^m \mid{} m,n\ge 0\}$. To prove that this set is pairwise distinguishable by the original language, I said that for all $m$ and $n$, $0^n1^m$ is distinguishable from all previous $0^i1^m,\:0\:\le i\le n-1$ because there exists a $z=0^n$ such that $0^n1^mz$ is an element of the original language but $0^i1^mz,\:0\le i\le n-1$ is not an element of the original language.
I first want to ask whether this was indeed the correct way to do the proof?
I am also quite confused for the second question as none of the strings are palindromes. So I am quite confused on how to approach the problem.
Any help would be highly appreciated!
Best Answer
For the first language, your idea is exactly correct.
$0^n1z \in L \iff z = 0^n$. Thus $0^n1$ and $0^m1$ are in separate equivalence classes for every $m \not = n$.
For the second, let's use $0^n1$ again. For $n \not = m$,
$0^n10^n \not \in L$ but $0^m10^n \in L$. Thus $0^n1$ and $0^m1$ are in separate equivalence classes, and the claim follows.
I hope this helps ^_^