In Chomskhy classification of formal languages, I need some examples of Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language(N-CFL)?

  1. Linear Language: For which Linear grammar is possible $( \subseteq CFG)$ e.g.
    $ L_{1} = \{a^nb^n | n \geq 0 \} $

Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g.
$ L_{2} = \{a^nb^nc^m | n \geq 0, m \geq 0 \} $
$L_{2}$is also a Non-Linear CFG (and unambiguous).

  1. Non-Deterministic Context Free Language(N-CFG): only Non-Deterministic Push-Down-Automata(N-PDA) is possible e.g.
    $ L_{3} = \{ww^{R} | w \in \{a, b\}^{*} \} $
    $L_{3}$ is also Linear CFG

Ambiguous CFL: CFL for which only ambiguous CFG is possible $ L_{4} = \{a^nb^nc^m | n \geq 0, m \geq 0 \} \bigcup \{a^nb^mc^m | n \geq 0, m \geq 0 \} $
$L_{4}$ is both non-linear and Ambiguous CFG And Every $ Ambigous CFL \subseteq NCFL$.


Whether all non-linear, Non-Deterministic CFL are Ambiguous?

If not then I need a example that is non-linear, non-deterministic CFL and also unambiguous?

Venn-diagram for Chomsky classification of formal languages.

enter image description here

  • $\begingroup$ cs.stackexchange.com/questions/109/… $\endgroup$
    – sdcvvc
    Oct 31, 2012 at 9:00
  • 2
    $\begingroup$ @sdcvvc: Your link doesn't answer this question, since the question there doesn't ask anything about linearity. $\endgroup$
    – Tara B
    Nov 27, 2012 at 11:03
  • $\begingroup$ @TaraB : The question is correct...To clear confusions I added the venn diagram...Which link is incorrect? $\endgroup$ Nov 27, 2012 at 11:17
  • 2
    $\begingroup$ @GrijeshChauhan: My comment was directed at sdvvc in regard to the link to the cs site, which I believe doesn't answer your question. I have no problems with your question. I wish I could answer it for you, but I don't know anything about linear grammars. $\endgroup$
    – Tara B
    Nov 27, 2012 at 12:33
  • $\begingroup$ @TaraB : Thanks! TaraB for your attention and concern.. :) .. $\endgroup$ Nov 27, 2012 at 12:50

1 Answer 1


Let $L$ be the language of well-formed expressions using a single type of brackets such as (()(()())). This language is nonlinear, deterministic and unambiguous.

Let $R$ be the language $\{w w^R\}$ of even palindromes. It is unambiguous, linear but nondeterministic.

Assume that alphabets of $L$ and $R$ are disjoint. Then $L \cup R$ is unambiguous, nonlinear (due to $L$), and nondeterministic (due to $R$).

  • $\begingroup$ So So So ..Thanks for your answer for the answer...I waiting since so long... $\endgroup$ Nov 30, 2012 at 15:23
  • $\begingroup$ I need one more favor ...may you place check the scope of ambiguous language I draw in my Venn-diagram. $\endgroup$ Nov 30, 2012 at 15:25
  • 1
    $\begingroup$ @Grijesh: I am not an expert, but it seems there exist linear ambiguous languages (google for "ambiguous linear languages"), so you'd need linear and ambiguous to intersect. Everything else on the diagram seems correct. $\endgroup$
    – sdcvvc
    Nov 30, 2012 at 19:49
  • $\begingroup$ @Grijesh: I encourage you to write in every area of the diagram an example of a language belonging there. $\endgroup$
    – sdcvvc
    Nov 30, 2012 at 20:25
  • 1
    $\begingroup$ you were correct there is also linear ambiguous language thanks! $\endgroup$ Dec 19, 2012 at 15:18

You must log in to answer this question.

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