I have a language:

$$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$

I want to prove that this language is regular. My first thought was to create a regular expression that accounts for all three of the cases of modulo 3 like such:

$$(aaa)^*(bbb)^* | a(aaa)^*b(bbb)^* | aa(aaa)^*bb(bbb)^*$$

However, this doesn't account for the fact that $j$ cannot equal $k$. Is there a way to exclude certain cases like this in a regular expression?

  • $\begingroup$ I'm not sure what "$j \equiv (k \bmod 3)$" means. $\endgroup$ May 27, 2020 at 8:07
  • 1
    $\begingroup$ If you meant "$j \equiv k \pmod 3$", then your language isn't regular. $\endgroup$ May 27, 2020 at 8:07
  • $\begingroup$ Sorry, that's what I meant. I fixed it. How you would know the language is not regular? $\endgroup$
    – Sakura M.
    May 27, 2020 at 8:09

1 Answer 1


Your language $L$ is not regular. Suppose that it was regular, then its complement $\overline{L}$ is also regular and the intersection $M = \{ a^j,b^k \mid j=k \vee j \not\equiv k \pmod{3} \}$ between $\overline{L}$ and $\{a^j,b^k \mid j,k \ge 0\}$ is regular.

Let $n$ a sufficiently large multiple of $3$ and consider the word $a^n b^n$. By the pumping lemma there is some $1 \le \ell \le n$ such that all words of the form $a^{n+i\ell} b^{n}$ belong to $M$, for all choices of an integer $i \ge -1$.

We pick $i=3$, so that the resulting word is $a^{n+3\ell} b^{n}$. Clearly $n+3\ell \equiv n \pmod{3}$ while $n+3\ell \neq n$. This shows that $a^{n+3\ell} b^{n} \not\in M$, a contradiction.


Your Answer

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

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