# Prove that a language is not regular using the pumping lemma

Could anyone tell me if I can prove nonregularity of given language using the pumping lemma like I did below? If my proof is wrong could anyone tell me how to prove that the language is not regular using the pumping lemma? $$L = \left\{ a^{m}b^{i}c^{n}\in L \mid (m,n,i \geq 0)\ \text{ and}\ ((m +n) \bmod 3 = 0 )\ \text{ and}\ ( m + n \geq i ) \right\}$$ I suppose that the language is regular. I know that $i,m,n \geq 0$ so I will choose a word from the language $w = b^{p}c^{3p}$. The condition $(m + n) \bmod 3 = 0$ should be fulfilled since $\forall p \geq 1 : 3p \bmod 3 = 0$. $$|w| \geq p$$ $$\underbrace{bbbb....b|}_p\underbrace{cccc......c}_{3p}\$$ Now I can decompose $w$ as $w=xyz$ with $\lvert y\rvert\geq 1$ and $\lvert xy\rvert\leq p$. $$x = b^{l},\ l\ge 0 \\y =b^{k} \,,k\ge 1 \\ z = b^{m}c^{3p} \,,m\ge0 \\(l+k+m=p) \ \text{ and}\ (l+k \leq p)$$ I'll try to pump $i$ so the word won't be in language $xy^{i}z$.

If I put $i = \frac{3p+1}{k}$ then I get: $$b^{l}b^{{k}{\frac{3p+1}{k}}}b^{m}c^{3p} = b^{l}b^{3p+1}b^{m}c^{3p}$$ which is not in $L$ because the amount of $b$ is greater than $c$.

• You wrote $a^{n}b^{i}c^{n}$ but I suppose it is either $a^{m}b^{i}c^{n}$ or $a^{n}b^{i}c^{m}$. Please check. Dec 24 '16 at 11:04

The problem with your proof is that $\frac{3p+1}{k}$ has no reason to be an integer.
Hint. In any case, you could first simplify your problem by using the following argument: if $L$ is regular, then the language $L \cap b^*c^*$ is also regular. Now $$L \cap b^*c^* = \{ b^ic^n \mid n \bmod 3 = 0 \ \text{ and }\ n \geqslant i \} = \{ b^ic^{3k} \mid 3k \geqslant i \}$$ Can you prove now that $\{ b^ic^{3k} \mid 3k \geqslant i \}$ is not regular?