Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 \} $

  2. 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).

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

4. 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$.

My Question is:

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

share|cite|improve this question
@sdcvvc: Your link doesn't answer this question, since the question there doesn't ask anything about linearity. – Tara B Nov 27 '12 at 11:03
@TaraB : The question is correct...To clear confusions I added the venn diagram...Which link is incorrect? – Grijesh Chauhan Nov 27 '12 at 11:17
@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. – Tara B Nov 27 '12 at 12:33
@TaraB : Thanks! TaraB for your attention and concern.. :) .. – Grijesh Chauhan Nov 27 '12 at 12:50
up vote 2 down vote accepted

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$).

share|cite|improve this answer
So So So ..Thanks for your answer for the answer...I waiting since so long... – Grijesh Chauhan Nov 30 '12 at 15:23
I need one more favor ...may you place check the scope of ambiguous language I draw in my Venn-diagram. – Grijesh Chauhan Nov 30 '12 at 15:25
@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. – sdcvvc Nov 30 '12 at 19:49
@Grijesh: I encourage you to write in every area of the diagram an example of a language belonging there. – sdcvvc Nov 30 '12 at 20:25
you were correct there is also linear ambiguous language thanks! – Grijesh Chauhan Dec 19 '12 at 15:18

Your Answer


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.