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

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

[Question]

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/… Oct 31, 2012 at 9:00
• @TaraB : The question is correct...To clear confusions I added the venn diagram...Which link is incorrect? Nov 27, 2012 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. Nov 27, 2012 at 12:33
• @TaraB : Thanks! TaraB for your attention and concern.. :) .. Nov 27, 2012 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$).