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

Question

In the Chomsky 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( ⊆ CFG) e.g.
   L₁ = {aⁿbⁿ | n ≥ 0 }

2. Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g.
   L₂ = {aⁿbⁿc^m | n ≥ 0, m ≥ 0 }
   L₂ is unambiguous.

A CF grammar that is not linear is nonlinear.
L_nl = {w: n_a(w) = n_b(w)} is also a Non-Linear CFG.

-- 3. Non-Deterministic Context Free Language(N-CFG): For which only Non-Deterministic Push-Down-Automata(N-PDA) is possible e.g.
L₃ = {ww^R | w ∈ {a, b}^* }
L₃ is also Linear CFG.

--4. Ambiguous CFL: CFL for which only ambiguous CFG is possible
L₄ = {aⁿbⁿc^m | n ≥ 0, m ≥ 0 } U {aⁿb^mc^m | n ≥ 0, m ≥ 0 }
L₄ is both non-linear and Ambiguous CFG And Every Ambigous CFL \subseteq N-CFL.

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?

Given Venn-diagram below:

Also asked here

Rizzio

Answer 1

"IN CONTEXT OF CHOMSHY CLASSIFICATION OF FORMAL LANGUAGE"

(1) L₃ = {ww^R | w ∈ {a, b}^* }

• Language L₃ is a Non-Deterministic Context Free Language, its also Unambiguous and Liner language.

(2) L_p is language of parenthesis matching. There are two terminal symbols "(" and ")".
Grammar for L_p is:

S → SS
S → (S)
S → ()   

• This language is nonlinear, deterministic and unambiguous too.

Language L that is union of L_p and L₃ is unambiguous, nonlinear (due to L_p), and non-deterministic (due to L₃) (Assuming language symbols for both languages are different).

This Language is an example of language in Venn-diagram for which I marked ??.

Also the correct diagram is below:

An ambiguous context free language also be a liner context free

Rizzio