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