Show that a language is not regular using the Myhill-Nerode Theorem

computer scienceregular-language

I need to show that the language below is not regular using the Myhill-Nerode Theorem, and I am currently a bit lost, how would I do that with this theorem?

Σ={a,b,c}

and

ADD={a^i b^j c^k ∣ i>=2 and GCD(j,k)=/=1}

Thank you in advance

Best Answer

According to Myhill-Nerode theorem, language $L$ is regular if and only if the number of equivalence classes of relation $R_L$, defined as $xR_L y \iff \{z\in T^*:xz \in L\}=\{z\in T^*:yz \in L\}$, where $T^*$ is the set of all words in given alphabet, is finite. If you take two words from $L$, $w_1=a^{i_1} b^p c^{k_1}$ and $w_2=a^{i_2} b^p c^{k_2}$, where $k_1 \neq k_2$ and $p$ is prime, $w_1c^m \in L \land w_2c^m \in L \iff \mathrm{GCD}(p,k_1+m) \neq 1 \land \mathrm{GCD}(p,k_2+m) \neq 1$. But $\mathrm{GCD}(p,k_1) \neq 1 \land \mathrm{GCD}(p,k_2) \neq 1$, which means $k_1$ and $k_2$ are equal $n_1p$ and $n_2p$, $n_1,n_2\geqslant2$, so $m$ must be proportional to $p$, too. Hence, $[a^2 b^p c^{2p}]=\{a^m b^p c^{np}:n\geqslant2, m\geqslant2\}$ and we found an infinite set of equivalence classes, because they are different for each prime $p$.

Related Question