Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite
1

Is it possible that an ambiguous context free language also be a liner context free.
I have doubt regarding scope of ambiguous language in below Venn-diagram.

enter image description here

share|improve this question

1 Answer

up vote 1 down vote accepted

If I am reading your observation in the right way, I believe you are right.

It was proved by Ogden (as an application of his famous Pumping Lemma) that $\{ a^ib^jc^k \mid i=j \mbox{ or } j=k \}$ is inherently ambiguous, meaning is has no unambiguous context-free grammar. At the same time the language is linear.

Thus, in the Venn-diagram the sets "Linear CFL" and "(inherently) Ambiguous CFL" should intersect.

share|improve this answer
Correct... I learnt about this language in peter Linz. Hendrik Jan except this every thing right na? – Grijesh Chauhan Dec 12 '12 at 13:31
1  
Yes, I think that is the only point that should be changed in the figure. – Hendrik Jan Dec 13 '12 at 15:42
Hendrik Jan ..Thanks!! – Grijesh Chauhan Dec 13 '12 at 16:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.