In Chomskhy classification of formal languages, I need some examples of Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language(N-CFL)?
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).
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.
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$).