# 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. Commented Sep 11, 2019 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. Commented Sep 11, 2019 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
Commented Sep 11, 2019 at 13:59
• I don't find any other decomposition which can be pumped. Can you please suggest one. Commented Sep 11, 2019 at 14:02
• I found the decomposition that works. $v = \lambda, \space y=c^k$ Commented Sep 12, 2019 at 0:35