Prove that this language is not regular

Question

I need to prove that the language $$L = \{a^nb^mc^k|n+k\neq3m\}$$

is not regular. Any ideas how I can do that?

Answer 1

Assume to the contrary that $L$ is regular. Then its complement $L^C$ is also regular. Now the language $A=\{a^ib^jc^k | i,j,k\in\mathbb{N}\}$ is clearly regular. (Automaton: first take $a$'s, then $b$'s then $c$'s) So we have that the language

$$L^C\cap A = \{a^nb^mc^k | n+k=3m\}$$

is regular. But this, I think, can be seen not to be regular (with the pumping lemma).

To see that "the language with equality sign" isn't regular: If it has pumping length $p$, take the word $a^pb^pc^{2p}$. The pumping part must be contained in the $a^p$ part, so it's just $a^t$ for some $t$. Pump it to break the equality.