Приложение

П.1. Неразрешимые проблемы
Контекстно-зависимые языки
Проблема пустоты: дана csg G .
Вопрос: L(G) = ∅?
Контекстно-свободные языки
Проблема пустоты пересечения: даны произвольные cfg G1 и G2.
Вопрос: L(G1) ∩ L(G2) = ∅?
Проблема полноты: дана cfg G, словарь терминалов которой есть Σ.
Вопрос: L(G) = Σ*?

Проблема принадлежности пересечения классу cfl: даны cfg G1 и G2.
Вопрос: L(G1) ∩ L(G2) — cfl?
Проблема принадлежности дополнения классу cfl: дана cfg G.
Вопрос: L(G) ⎯ cfl?
Проблема регулярности языка: дана cfg G. Вопрос: L(G) — rs?

Неоднозначность cfg: дана произвольная cfg G.
Вопрос: G — однозначна?
Проблема существенной синтаксической неоднозначности cfl: дана произвольная cfg G.
Вопрос: L(G) — существенно однозначен?

=∅?
5)
Детерминированные cfl
Даны языки L1 и L2, распознаваемые dpda.
Вопросы:
1) L1∩ L2 = ∅?
2) L1∩ L2 — cfl?
3) L1∪ L2 — детерминированный cfl?
4) L1⊆ L2?

=∅?
5)
П.2. Разрешимые проблемы,
касающиеся детерминированных
контекстно-свободных языков
Некоторые вопросы, которые не разрешимы для контекстно-свободных языков в общем случае, разрешимы для детерминированных языков.

=∅?
5)