17 views
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.
| 17 views
0

this grammar is linear and consequently language too is linear.

yes.

linear language is a language generated by some linear grammar.

0
Thanks for answer. And I found that problem was with my selection of $v$ and $y$. If we choose $v=\lambda$ then string can be pumped without any issue.