¿Ejemplo de CFL no lineales, no ambiguas y no deterministas?
En la clasificación de Chomsky de los lenguajes formales, necesito algunos ejemplos deNon-Linear, Unambiguous and also Non-Deterministic
¿Lenguaje libre de contexto (N-CFL)?
Lenguaje lineal: Porcual gramatica lineal es posible (⊆ CFG) por ej.
L1 = {anbn | n ≥ 0}
Lenguaje libre de contexto determinista (D-CFG): Para el cual es posible un autómata push-down determinístico (D-PDA), p. Ej.
L2 = {anbncm | n ≥ 0, m ≥ 0}
L2 es inequívoco
Una gramática CF que esno lineal no es lineal.
Lnl = {w: na(w) = nb(w)} es también unCFG no lineal.
- 3.Lenguaje libre del contexto no determinista (N-CFG): Para cualonly Non-Deterministic Push-Down-Automata(N-PDA)
es posible por ejemplo
L3 = {wwR | w ∈ {a, b}* }
L3 También es lineal CFG.
--4.CFL ambigua: CFL para los cualesonly ambiguous CFG is possible
L4 = {anbncm | n ≥ 0, m ≥ 0} U {anbmcm | n ≥ 0, m ≥ 0}
L4 es tanto CFG ambiguo como no lineal y cada CFL ambiguo \ subseteq N-CFL.
Mi pregunta es:
¿Todos los CFL no lineales, no deterministas son ambiguos? Si no es así, necesito un ejemplo que no sea lineal, CFL no determinista y también no ambiguo.
Dado el diagrama de Venn a continuación:
Tambien preguntoaquí