1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ The second language doesn't contain any palindromes, by definition! $\endgroup$ – Yuval Filmus Sep 27 at 0:31
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.