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)? Linear Language: For which Linear grammar is possible( ⊆ CFG) e.g. L1 = {anbn | n ≥ 0 } Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g. L2 = {anbncm | n ≥ 0, m ≥ 0 } L2 is unambiguous. A CF grammar that is not linear is nonlinear. Lnl = {w: na(w) = nb(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. L3 = {wwR | w ∈ {a, b}* } L3 is also Linear CFG. --4. Ambiguous CFL: CFL for which `only ambiguous CFG is possible` L4 = {anbncm | n ≥ 0, m ≥ 0 } U {anbmcm | n ≥ 0, m ≥ 0 } L4 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…

Accepted Answer

"IN CONTEXT OF CHOMSHY CLASSIFICATION OF FORMAL LANGUAGE"

(1) L3 = {wwR | w ∈ {a, b}* }

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

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

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

- This language is nonlinear, deterministic and unambiguous too.

Language L that is union of Lp and L3 is unambiguous, nonlinear (due to Lp), and non-deterministic (due to L3) (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

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

Solution

Problem