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$!

  • $\begingroup$ 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). $\endgroup$
    – momos
    May 21 at 17:52
  • $\begingroup$ Technically, $y$ could contain $c$'s, but overall you have the idea. $\endgroup$
    – Nathaniel
    May 21 at 18:07
  • $\begingroup$ So i would have to make several cases? $\endgroup$
    – momos
    May 21 at 18:10
  • $\begingroup$ Yes, and find a contradiction in each case. $\endgroup$
    – Nathaniel
    May 21 at 18:11
  • $\begingroup$ Thank you very much! $\endgroup$
    – momos
    May 21 at 18:12

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.