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

Question

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!

Answer 1

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

With a bit more work, you can show that in fact all words are pairwise distinguishable. See for example here or here.