How to show that the language containing the words which number of $b$ divides the number of $a$ isn't regular using Myhill-Nerode theorem?

Question

I want to show that the language containing the words which number of $b$ divides the number of $a$ isn't regular using Myhill-Nerode theorem which is the following :

$L$ is a regular language if and only if the number of equivalence classes of ∼ relation for all $L$ is finite.

I know how to show that the Language containing a number of $a$ which is equal to the number of $b$ isn't regular with the thoerem :

We first show that the complement of $L$ isn't regular : This language contains words for which the number of $a$ is equal with the number of $b$. The proof is the same I made up for $L=a^ib^i$ works without any changement here : we take $w_k=a^k$. Two words $w_i$ and $w_j$ are distinguished by $b^i$.

Therefore we can say that $L$ isn't regular because regular languages are closed by complementation.

But how to show that the words which number of $b$ divides the number of $a$ isn't regular using Myhill-Nerode theorem ?

Answer 1

The same thing works: let $i<j$, then $a^i$ and $a^j$ are distinguished by $b^i$.

Answer 2

You need to show that ~$_L$ has infinite equivalent classes.

For example take $x_n = b \ ^ n$ , so $\{x_n \}_{n = 0} ^\infty \subset L$.

Given $n \ne m$ , take $z_n = b \ ^n a \ ^ {2n}$ , we have $x_nz_n \in L$ but

$x_mz_n = b \ ^ m b \ ^ na \ ^ n= b \ ^ {n+m} a \ ^ {2n}$ and $n+m$ does not

divide $2n$ , thus $x_n$ and $x_m$ are not equivalent in ~$_L$ , so ~$_L$ has

infinite equivalent classes, and therefore by Myhill-Nerode theorem , $L \notin REG$.