# How to create a regular expression for this language?

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?

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

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.