Proving regularity with pumping lemma

Question

I have to prove , that language is not regular using pumping lemma.

$L = \{ ccc a^k b^l , k > 2 , l >= k \}$

the language i choose is

$ccca^{p+2}b^{p+3}$

So i should have multiple decompositions e.g

1)

x = ccc

y = $a^{k}$ ; k > 0; k <= p

z = $a^{l}b^{p+3}$ ; l > 0 ; l + k = p + 2

2)

x = c

y = cc$a^{k}$ ; k >= 0; k <= p - 2

z = $a^{l}b^{p+3}$ ; l > 0 ; l + k = p + 2

3)

x = $\epsilon$

y = ccc$a^{k}$ ; k >= 0; k <= p-3

z = $a^{l}b^{p+3}$ ; l > 0 ; l + k = p + 2

4)

x = cc

y = c$a^{k}$ ; k >= 0; k <= p - 1

z = $a^{l}b^{p+3}$ ; l > 0 ; l + k = p + 2

I cannot create one univeral decomposition due to rules of k and l differ.

So i have to find index i so $xy^{i}z\notin L$ for all those 4 decomposition? Also did i miss any decomposition or is this everything i can do?

thanks for answers and help!

Answer 1

You don't really need to be that exhaustive for the decompositions.

Let $p\geq1$ and consider the word $w=c^3a^{p+2}b^{p+2}\in L$. We do have $\lvert w\rvert=2p+7\geq p$. Decompose $w$ as $w=xyz$ with $\lvert y\rvert\geq1$ and $\lvert xy\rvert\leq p$. Notice that since $\lvert c^3a^p\rvert=p+3$, $xy$ is a subword of $c^3a^p$. You only have $2$ cases to consider:

• If $y$ contains a $c$, then the word $xz$ will have less than three $c$'s, so $xz\not\in L$.
• If $y$ contains no $c$'s, then $y$ contains only $a$'s, say $k\geq1$ of them. Then $xy^2z=c^3a^{p+2+k}b^{p+2}\not\in L$