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

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

3 Проблемы отношений между cfl и rs: даны cfg G и rs R. Вопросы: 1) L(G) = R? 2) L(G) R? 3) L(G) = Проблемы эквивалентности и вложенности: даны cfg G 1 и G 2. Вопросы: 1) L(G 1 ) = L(G 2 ) 2) L(G 1 ) L(G 2 ) Приложение

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

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

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

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

8 = 5) Даны детерминированный cfl L и rs R. Разрешимы следующие вопросы: 1) L существенно неоднозначен? 2) L = R? 3) L rs? 4) 5) контекстно-свободный язык? 6) L R? Приложение

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