search
Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points

  3. GAITONDE

    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points

  6. BLACK_CLOUD

    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

0 votes
10 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.
in Theory of Computation 199 points 10 views
0

this grammar is linear and consequently language too is linear.

yes.

 

linear language is a language generated by some linear grammar.

https://en.wikipedia.org/wiki/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.

1 Answer

...