Awesome q2a theme
0 votes
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.
in Theory of Computation by (911 points) | 17 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

0 votes
by (1.2k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Feb 2020
  1. shashin

    363 Points

  2. Shaik Masthan

    79 Points

  3. SuvasishDutta

    39 Points

  4. srestha

    33 Points

  5. Mk Utkarsh

    32 Points

  6. neeraj_bhatt

    31 Points

  7. !KARAN

    30 Points

  8. Debapaul

    23 Points

  9. Pratyush Priyam Kuan

    18 Points

  10. kalra05

    18 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
3,327 questions
1,581 answers
10,280 comments
89,915 users