2

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?

rubik
  • 9,344
Dilyan Traykov
  • 43
  • 1
    Have you tried pumping lemma? – ploosu2 Feb 09 '15 at 22:51
  • I'm trying to figure out how to use it in this particular example, but I'm stuck. – Dilyan Traykov Feb 09 '15 at 22:54
  • Ok, maybe the pumping lemma isn't the way to go directly in this case. Seems a bit tricky. What about closure properties of regular languages. If you had equality in the definition of $L$, it would be easy... OK now I think I see how to solve it. Do you want me to post a solution or is hint enough? – ploosu2 Feb 09 '15 at 23:52
  • I'd prefer the solution as I don't think I can come up with it on my own. – Dilyan Traykov Feb 09 '15 at 23:54
  • OK. I actually had some already typed so I don't have to waste it :D. – ploosu2 Feb 09 '15 at 23:56

1 Answers1

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.

ploosu2
  • 8,707