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$
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, privacy policy and cookie policy

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