# Proving a language is not regular using the Myhill-Nerode Theorem

I have to prove that the following languages are not regular using the Myhill-Nerode Theorem.

1. $$\{0^{n}1^{m}0^{n} \mid{} m,n \ge 0\}$$
2. $$\{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 I can't even seem to find a string that is part of the language but is a palindrome. All the strings other than the empty string in that language are not palindromes. So I am quite confused on how to approach the problem.

Any help would be highly appreciated!

• The second language doesn't contain any palindromes, by definition! Sep 27, 2019 at 0:31

The words $$0^n1$$ are pairwise distinguishable, since $$0^n10^n$$ is a palindrome but $$0^n10^m$$ isn't (for $$n \neq m$$).