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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Correct... I learnt about this language in peter Linz. Hendrik Jan except this every thing right na? $\endgroup$ Dec 12, 2012 at 13:31
  • 1
    $\begingroup$ Yes, I think that is the only point that should be changed in the figure. $\endgroup$ Dec 13, 2012 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .