Пример нелинейного, недвусмысленного и недетерминированного КЛЛ?

Question

В классификации формальных языков Хомского мне нужны примеры Non-Linear, Unambiguous and also Non-Deterministic Контекст-Free-Language(N-CFL)?

1. Линейный язык: для которого возможна линейная грамматика ( ⊆ CFG), например
   L ₁ = {a ⁿ b ⁿ | n ≥ 0}

2. Детерминированный контекстно-свободный язык (D-CFG): для которого возможны детерминированные автоматические нажатия (D-PDA), например
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0}
   L ₂ однозначно.

Нелинейная грамматика CF является нелинейной.
L _nl = {w: n _a (w) = n _b (w)} также является нелинейным CFG.

- 3. Недетерминированный контекстно-свободный язык (N-CFG): для которого only Non-Deterministic Push-Down-Automata(N-PDA) возможно, например
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃ также является линейным CFG.

--4. Неоднозначный КЛЛ: КЛЛ, для которого only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0} U {a ⁿ b ^m c ^m | n ≥ 0, m ≥ 0}
L ₄ является как нелинейным, так и неоднозначным CFG и каждым неоднозначным CFL \subseteq N-CFL.

Мой вопрос:
Все ли нелинейные, недетерминированные КЛЛ являются неоднозначными? Если нет, то мне нужен пример, который является нелинейным, недетерминированным КЛЛ и также однозначным?

Приведенная ниже диаграмма Венна:

Также спросили здесь

Answer 1

"В КОНТЕКСТЕ ХОМСКОЙ КЛАССИФИКАЦИИ ФОРМАЛЬНОГО ЯЗЫКА"

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

• Язык L₃ является недетерминированным контекстно-свободным языком, он также является однозначным и линейным языком.

(2) L_p - язык сопоставления скобок. Есть два терминальных символа "(" и ")".
Грамматика для л_р это:

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

• Этот язык является нелинейным, детерминированным и однозначным.

Язык L, который является объединением L_p и L_3, является однозначным, нелинейным (из-за L_p) и недетерминированным (из-за L₃) (при условии, что символы языка для обоих языков различны).

Этот язык является примером языка в диаграмме Венна, для которого я отметил ??,

Также правильная схема ниже:

Неоднозначный контекстно-свободный язык также может быть свободным от контекста.