- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Приложение презентация
Содержание
- 1. Приложение
- 2. П.1. Неразрешимые проблемы Контекстно-зависимые языки Проблема пустоты:
- 4. Проблема принадлежности пересечения классу cfl: даны cfg
- 5. Неоднозначность cfg: дана произвольная cfg G.
- 6. =∅? 5) Детерминированные cfl Даны
- 7. =∅? 5) П.2. Разрешимые проблемы,
- 8. =∅? 5)
- 9. Нерешенная проблема — неизвестно, разрешима или нет
Слайд 2П.1. Неразрешимые проблемы
Контекстно-зависимые языки
Проблема пустоты: дана csg G .
Вопрос: L(G)
= ∅?
Контекстно-свободные языки
Проблема пустоты пересечения: даны произвольные cfg G1 и G2.
Вопрос: L(G1) ∩ L(G2) = ∅?
Проблема полноты: дана cfg G, словарь терминалов которой есть Σ.
Вопрос: L(G) = Σ*?
Контекстно-свободные языки
Проблема пустоты пересечения: даны произвольные cfg G1 и G2.
Вопрос: L(G1) ∩ L(G2) = ∅?
Проблема полноты: дана cfg G, словарь терминалов которой есть Σ.
Вопрос: L(G) = Σ*?
Слайд 4Проблема принадлежности пересечения классу cfl: даны cfg G1 и G2.
Вопрос:
L(G1) ∩ L(G2) — cfl?
Проблема принадлежности дополнения классу cfl: дана cfg G.
Вопрос: L(G) ⎯ cfl?
Проблема регулярности языка: дана cfg G. Вопрос: L(G) — rs?
Проблема принадлежности дополнения классу cfl: дана cfg G.
Вопрос: L(G) ⎯ cfl?
Проблема регулярности языка: дана cfg G. Вопрос: L(G) — rs?
Слайд 5Неоднозначность cfg: дана произвольная cfg G.
Вопрос: G — однозначна?
Проблема
существенной синтаксической неоднозначности cfl: дана произвольная cfg G.
Вопрос: L(G) — существенно однозначен?
Вопрос: L(G) — существенно однозначен?
Слайд 6 =∅?
5)
Детерминированные cfl
Даны языки L1 и L2, распознаваемые dpda.
Вопросы:
1)
L1∩ L2 = ∅?
2) L1∩ L2 — cfl?
3) L1∪ L2 — детерминированный cfl?
4) L1⊆ L2?
2) L1∩ L2 — cfl?
3) L1∪ L2 — детерминированный cfl?
4) L1⊆ L2?
Слайд 7 =∅?
5)
П.2. Разрешимые проблемы,
касающиеся детерминированных
контекстно-свободных языков
Некоторые вопросы, которые не разрешимы для контекстно-свободных языков в общем случае, разрешимы для детерминированных языков.
Слайд 9Нерешенная проблема — неизвестно, разрешима или нет следующая проблема: даны детерминированные
магазинные автоматы M1 и M2.
Вопрос: T(M1) = T(M2)?
Вопрос: T(M1) = T(M2)?
