# In Context of Chomskhy classification of formal languages

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.

-

## 1 Answer

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.

-
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
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