0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – J.-E. Pin
    Dec 24 '16 at 11:04
1
$\begingroup$

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?

$\endgroup$

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.