Приложение


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

3


Slide 3

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


Slide 4

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


Slide 5

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


Slide 6

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


Slide 7

8 =?? 5)


Slide 8

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


×

HTML:





Ссылка: