'

Приложение

Понравилась презентация – покажи это...





Слайд 0

1 Приложение НЕРАЗРЕШИМЫЕ И РАЗРЕШИМЫЕ ПРОБЛЕМЫ, КАСАЮЩИЕСЯ ФОРМАЛЬНЫХ ЯЗЫКОВ


Слайд 1

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


Слайд 2

3


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

8 =?? 5)


Слайд 8

9 Нерешенная проблема — неизвестно, разрешима или нет следующая проблема: даны детерминированные магазинные автоматы M1 и M2. Вопрос: T(M1) = T(M2)?


×

HTML:





Ссылка: