# Show that a language with union is not regular by using pumping lemma

Given the language $$L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \ \vert w\vert_a \ = \ \vert w\vert_b \} \ \cup \ \{ a,b \}^* }$$

I'm really unsure how to even start because of the union.

I tried it with $$w=a^nb^n$$ but my correction said that it's pumpable because it is in $$\{ a,b \}^*$$ which makes sense.

What would be a good word to start with? I guess there are several cases i need to show?

If $$L$$ was regular, so would be $$L \cap c^+\Sigma^* = \{c^{2k}w\mid k\geq 1, w\in\{a,b,c\}^* \text{ and }|w|_a = |w|_b\}$$.
That means that if you prove that this language is not regular, then $$L$$ cannot be regular too (that way, we got rid of the union).
Now you can take it from here with pumping lemma, starting from $$c^2a^nb^n$$!
• Thanks for the answer. I tried to make a little "sketch". So i take the word c^2a^nb^n as you said. Because |xy| <= n and |y| >= 1, y has to be y = a^k and 1<=k<=n. With that i can pump xyz to xyyz and get c^2a^(n+k)b^n which is it not regular because the amount of as and bs is not the same. Would this make sense or did i miss something (I feel like i did). May 21 at 17:52
• Technically, $y$ could contain $c$'s, but overall you have the idea. May 21 at 18:07