Przykład nieliniowej, niejednoznacznej i nie deterministycznej CFL?
W klasyfikacji języków formalnych Chomsky'ego potrzebuję przykładówNon-Linear, Unambiguous and also Non-Deterministic
Język bezkontekstowy (N-CFL)?
Język liniowy: Dlaktóra gramatyka liniowa jest możliwe (G CFG) np.
L1 = {anbn | n ≥ 0}
Język deterministyczny bez kontekstu (D-CFG): Dla których możliwe są deterministyczne push-down-automaty (D-PDA), np.
L2 = {anbncm | n ≥ 0, m ≥ 0}
L2 jest jednoznaczny.
Gramatyka CF, która jestnie liniowy jest nieliniowy.
Lnl = {w: na(w) = nb(w)} jest również aNieliniowe CFG.
- 3.Nie deterministyczny język bezkontekstowy (N-CFG): Dla któregoonly Non-Deterministic Push-Down-Automata(N-PDA)
jest możliwe np.
L3 = {wwR | w ∈ {a, b}* }
L3 jest także Linear CFG.
--4.Niejednoznaczne CFL: CFL, dla któregoonly ambiguous CFG is possible
L4 = {anbncm | n ≥ 0, m ≥ 0} U {anbmcm | n ≥ 0, m ≥ 0}
L4 jest nieliniowym i niejednoznacznym CFG i każdym Ambigous CFL subteteq N-CFL.
Moje pytanie brzmi:
Czy wszystkie nieliniowe, nie-deterministyczne CFL są niejednoznaczne? Jeśli nie, to potrzebuję przykładu, który jest nieliniowy, niedeterministyczny CFL, a także jednoznaczny?
Biorąc pod uwagę diagram Venna poniżej:
Zapytałem teżtutaj