0
$\begingroup$

I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$.

Now, I wanted to determine whether this language is linear or not.

So, I came up with this grammar:

$S \rightarrow A\thinspace|\thinspace Sc$

$A \rightarrow aAb \thinspace | \thinspace \lambda$

I'm pretty sure(not completely however) that this grammar is linear and consequently language too is linear.

Now, when I use pumping lemma of linear languages with $w$, $v$ and $u$ chosen as follow I find that this language is not linear.

$w = a^nb^nc^m, \space v = a^k, \space y=c^k$

$w_0 = a^{n-k}b^nc^{n-k}$

now, $w_0 \notin L \space (\because n_a \neq n_b)$

So, I'm unable to find whether the language is linear or not and what goes wrong in above logic with either case. Please help.

Improve this question
$\endgroup$
5
  • $\begingroup$ Please recheck your attempt to disprove that the language is linear, you mixed up some symbols there but you also seem to use the Pumping Lemma for regular languages. $\endgroup$ – ttnick Sep 11 '19 at 12:19
  • $\begingroup$ @ttnick I believe(or unable to find exact flaw in my argument) that I'm using pumping lemma of linear languages as $w$ is chosen such that it satisfies the premises of pumping lemma of linear languages($\because |w| \ge m$) and $1 \le |vy| \le m$. Can you be more specific where there is a flaw. $\endgroup$ – Vimal Patel Sep 11 '19 at 12:59
  • $\begingroup$ The pumping lemma says that there exists a decomposition which can be pumped. It doesn't say that every decomposition can be pumped. $\endgroup$ – rici Sep 11 '19 at 13:59
  • $\begingroup$ I don't find any other decomposition which can be pumped. Can you please suggest one. $\endgroup$ – Vimal Patel Sep 11 '19 at 14:02
  • $\begingroup$ I found the decomposition that works. $v = \lambda, \space y=c^k$ $\endgroup$ – Vimal Patel Sep 12 '19 at 0:35

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.