1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I'm not sure what "$j \equiv (k \bmod 3)$" means. $\endgroup$ – Yuval Filmus May 27 '20 at 8:07
  • 1
    $\begingroup$ If you meant "$j \equiv k \pmod 3$", then your language isn't regular. $\endgroup$ – Yuval Filmus May 27 '20 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 '20 at 8:09
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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