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 is non-linear, non-deterministic CFL and also unambiguous?
Given Venn-diagram below:
Also asked here
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…