# Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?

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. • cs.stackexchange.com/questions/109/… – sdcvvc Oct 31 '12 at 9:00
• @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

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