# Whether following language is linear or not?

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.

• 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. – ttnick Sep 11 at 12:19
• @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. – Vimal Patel Sep 11 at 12:59
• The pumping lemma says that there exists a decomposition which can be pumped. It doesn't say that every decomposition can be pumped. – rici Sep 11 at 13:59
• I don't find any other decomposition which can be pumped. Can you please suggest one. – Vimal Patel Sep 11 at 14:02
• I found the decomposition that works. $v = \lambda, \space y=c^k$ – Vimal Patel Sep 12 at 0:35