1
$\begingroup$

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

1 Answers 1

1

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.

  • 1
    Yes, I think that is the only point that should be changed in the figure.2012-12-13