Пример нелинейного, недвусмысленного и недетерминированного КЛЛ?
В классификации формальных языков Хомского мне нужны примеры Non-Linear, Unambiguous and also Non-Deterministic
Контекст-Free-Language(N-CFL)?
Линейный язык: для которого возможна линейная грамматика ( ⊆ CFG), например
L 1 = {a n b n | n ≥ 0}Детерминированный контекстно-свободный язык (D-CFG): для которого возможны детерминированные автоматические нажатия (D-PDA), например
L 2 = {a n b n c m | n ≥ 0, m ≥ 0}
L 2 однозначно.
Нелинейная грамматика CF является нелинейной.
L nl = {w: n a (w) = n b (w)} также является нелинейным CFG.
- 3. Недетерминированный контекстно-свободный язык (N-CFG): для которого only Non-Deterministic Push-Down-Automata(N-PDA)
возможно, например
L 3 = {ww R | w ∈ {a, b} * }
L 3 также является линейным CFG.
--4. Неоднозначный КЛЛ: КЛЛ, для которого only ambiguous CFG is possible
L 4 = {a n b n c m | n ≥ 0, m ≥ 0} U {a n b m c m | n ≥ 0, m ≥ 0}
L 4 является как нелинейным, так и неоднозначным CFG и каждым неоднозначным CFL \subseteq N-CFL.
Мой вопрос:
Все ли нелинейные, недетерминированные КЛЛ являются неоднозначными? Если нет, то мне нужен пример, который является нелинейным, недетерминированным КЛЛ и также однозначным?
Приведенная ниже диаграмма Венна:
Также спросили здесь
1 ответ
"В КОНТЕКСТЕ ХОМСКОЙ КЛАССИФИКАЦИИ ФОРМАЛЬНОГО ЯЗЫКА"
(1) L3 = {wwR | w ∈ {a, b}* }
- Язык L3 является недетерминированным контекстно-свободным языком, он также является однозначным и линейным языком.
(2) Lp - язык сопоставления скобок. Есть два терминальных символа "(" и ")".
Грамматика для лр это:
S → SS
S → (S)
S → ()
- Этот язык является нелинейным, детерминированным и однозначным.
Язык L, который является объединением Lp и L3, является однозначным, нелинейным (из-за Lp) и недетерминированным (из-за L3) (при условии, что символы языка для обоих языков различны).
Этот язык является примером языка в диаграмме Венна, для которого я отметил ??
,
Также правильная схема ниже:
Неоднозначный контекстно-свободный язык также может быть свободным от контекста.