Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
