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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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?
