2
$\begingroup$

The language is given by: $$L=\{a^nb^m|n<m\}$$ I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence. Any help would be appreciated.

$\endgroup$

1 Answer 1

4
$\begingroup$

You have to find an infinite set of strings $s_i$ such that for every two strings $s_i ≠ s_j$, there is a string $t_{ij}$ such that exactly one of $s_i t_{ij}$ and $s_j t_{ij}$ is in the language, and the other is not.

Now if you look at $a^n$ and $a^m$, n ≠ m, can you find a string t such that exactly one of $a^n t$ and $a^m t$ is in the language, and the other is not?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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