0
$\begingroup$

Could anyone tell me If I can prove regularity of given language using pumping lemma like I did below? If my prove is wrong could anyone tell me how to prove that the language is not regular using pumping lemma?

$$ L = \left\{ a^{n}b^{i}c^{n}\in L \mid (m,n,i >=0)\ and\ ((m +n)\%3 = 0 ) \ and\ ( m + n >= i ) \right\} $$

I suppose that the language is regular. I know that $i,m,n >= 0$ so I will choose word from the language $w = b^{p}c^{3p}$. The condition $(m + n) \% 3 = 0$ should be fulfilled since $\forall p >= 1 : 3p \%3 = 0$.

$$|w| >= p$$

$$ \underbrace{bbbb....b|}_p\underbrace{cccc......c}_{3p}\ $$ Now i can decompose $w$ as $w=xyz$ with $\lvert y\rvert\geq1$ 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) \ 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 from the L because the amount of b is greater than c.

$\endgroup$
  • $\begingroup$ Are you sure $3p+1$ will always be divisible by $k$? $\endgroup$ – Rick Decker Dec 23 '16 at 17:16
  • $\begingroup$ @RickDecker Does it matter? Because the k will be canceled by another k so in the end there only 3p + 1? $\endgroup$ – kvway Dec 23 '16 at 19:10
  • $\begingroup$ This is a nearly valid proof that the language is not regular. (In fact, proving that a language is not regular is the way the pumping lemma is usually used - it can't be used to prove that a language is regular) The one change I'd make is to address @RickDecker's complaint above: set $i$ equal to just $3p+1$ - forget the division. Since $k \geq 1$, you're guaranteed to have too many "b" characters. $\endgroup$ – Daniel Martin Dec 24 '16 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.