Проблема эквивалентности конечных автоматов

Теорема 15.6.1. Существует алгоритм, позволяющий по произвольным двум праволинейным грамматикам G₁ и G₂ узнать, верно ли, что .

Теорема 15.6.2. Существует алгоритм, позволяющий по произвольным двум праволинейным грамматикам G₁ и G₂ узнать, верно ли, что L(G₁) = L(G₂).

Упражнение 15.6.3. Эквивалентны ли грамматика

и грамматика

15.7*. Проблема эквивалентности детерминированных МП-автоматов

Теорема 15.7.1. Существует алгоритм, позволяющий по произвольным двум детерминированным МП-автоматам M₁ и M₂ узнать, верно ли, что L(M₁) = L(M₂).

Эту теорему доказал Жеро Сенизерг (Geraud Senizergues) в 1997 году. Упрощенное доказательство приводится в [Sti].

Упражнение 15.7.2. Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?

Упражнение 15.7.3. Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?

15.8*. Классы P и NP

Определение 15.8.1. Пусть машина Тьюринга M допускает язык L. Говорят, что язык L распознается за полиномиальное время на машине M, если существует такой многочлен p, что любое слово принимается машиной M не более чем за p(|w|) тактов.

Определение 15.8.2. Через P обозначается класс тех языков, которые распознаются за полиномиальное время на некоторой детерминированной машине Тьюринга.

Определение 15.8.3. Через NP обозначается класс тех формальных языков, которые распознаются за полиномиальное время на некоторой (в общем случае недетерминированной) машине Тьюринга.

Замечание 15.8.4. Очевидно, что . Неизвестно, совпадают ли классы P и NP.

Теорема 15.8.5. Все языки из класса NP являются разрешимыми.

Определение 15.8.6. Всюду определенная функция f из в называется вычислимой за полиномиальное время, если ее вычисляет некоторая детерминированная машина Тьюринга M (если , то данная функция fрассматривается как частичная функция из в ) и существует такой многочлен p, что для любого слова машина M вычисляет значение f(w) не более чем за p(|w|) тактов.

Определение 15.8.7. Язык полиномиально сводится (is polynomial time reducible) к языку , если существует такая вычислимая за полиномиальное время всюду определенная функция f из в , что для любого слова условие равносильно условию .

Определение 15.8.8. Формальный язык L называется NP- сложным (NP-hard}, если каждый язык из класса NPполиномиально сводится к языку L.

Определение 15.8.9. Формальный язык называется NP- полным (NP-complete), если он принадлежит классу NP и является NP -сложным.

Определение 15.8.10. Алгоритмическая проблема, относящаяся к некоторой задаче распознавания, называется NP- полной, если множество кодов индивидуальных задач с ответом "да" является NP-полным языком.

Теорема 15.8.11 (теорема Кука-Левина). Проблема выполнимости булевых формул в конъюнктивной нормальной форме N- полна.

Доказательство можно найти, например, в [Сэв, с. 325-328] или [ГэрДжо, с. 57-63].

Упражнение 15.8.12. Существует ли такой язык из класса P, что язык не принадлежит классу P?

Упражнение 15.8.13. Существуют ли такие языки L₁ и L₂ из класса P, что язык не принадлежит классу P?

Упражнение 15.8.14. Существуют ли такие языки L₁ и L₂ из класса NP, что язык не принадлежит классу NP?

15.9*. Проблема неравенства регулярных выражений без итерации

Теорема 15.9.1. Проблема неравенства регулярных выражений без итерации (то есть регулярных выражений с нулевой звездной высотой) NP- полна.

Доказательство. По регулярному выражению без итерации легко построить конечный автомат с однобуквенными переходами, не содержащий циклов. Проблема неравенства таких конечных автоматов принадлежит классу NP: достаточно "угадать" слово, принадлежащее разности языков, распознаваемых двумя данными автоматами, и, продвигаясь по этому слову буква за буквой, подобно доказательству теоремы 2.7.1 вычислять, в каких состояниях автоматы могут оказаться. При этом длину слова можно ограничить максимумом числа состояний двух автоматов.

Осталось доказать, что проблема неравенства регулярных выражений без итерации NP-сложна. Для этого достаточно продемонстрировать, что к этой проблеме полиномиально сводится проблема выполнимости булевых формул в конъюнктивной нормальной форме (то есть множество кодов выполнимых булевых формул в конъюнктивной нормальной форме полиномиально сводится к множеству кодов пар неравных регулярных выражений без итерации). Искомое полиномиальное сведЕние может быть построено следующим образом.

Пусть дана булева формула , составленная из пропозициональных переменных x₁, x₂,..., x_n (при более формальном подходе можно считать x_i обозначением слова p#ⁱ, как это сделано в примере 7.2.8). Здесь для каждого формула C_j является элементарной дизъюнкцией. Для краткости будем обозначать отрицание переменной x_i через (а не через , как в примере 7.2.8).

Построим два регулярных выражения над алфавитом . В качестве первого регулярного выражения возьмем

Для удобства отождествим истинностные значения "ложь" и "истина" с символами a и b соответственно. Тогда оценку пропозициональных переменных x₁, x₂,..., x_n можно естественным образом отождествить со словом длины n в алфавите . Второе регулярное выражение e построим так, чтобы выполнялось равенство

Если m = 1, то это сделать легко. Возьмем в качестве e произведение n сомножителей, каждый из которых совпадает с~одним из следующих четырех регулярных выражений: (a + b), a, b, 0. При этом i -й сомножитель соответствует пропозициональной переменной x_i и выбирается следующим образом:

· если данная элементарная дизъюнкция не содержит ни литерала x_i, ни литерала , то используем выражение (a+b);

· если она содержит литерал x_i, но не содержит литерала , то используем выражение a;

· если она содержит литерал , но не содержит литерала x_i, то используем выражение b;

· если она содержит оба литерала x_i и , то используем выражение 0.

Если m > 1, то построим по указанному методу для каждой из булевых формул C₁, C₂,..., C_m регулярное выражение и возьмем их сумму.

Легко видеть, что два построенных так регулярных выражения равны тогда и только тогда, когда булева формула невыполнима.

Пример 15.9.2. Пусть . Регулярные выражения

(a+b)(a+b)(a+b)

и

ab(a+b)+(a+b)ab+b(a+b)(a+b)+(a+b)(a+b)a

равны, так как булева формула

невыполнима (или, другими словами, булева формула

является тавтологией).

Упражнение 15.9.3. Равны ли регулярные выражения

(a+b)(a+b)(a+b)

и

bb(a+b)+ba(a+b)+a(a+b)b+(a+b)aa?

Упражнение 15.9.4. Равны ли регулярные выражения

(a+b)(a+b)(a+b)(a+b)

и

aab(a+b)+a(a+b)(a+b)b+(a+b)aa(a+b)+(a+b)bb(a+b)+

                    +(a+b)baa+bab(a+b)+b(a+b)(a+b)b?

Упражнение 15.9.5. Эквивалентен ли конечный автомат

конечному автомату, изображенному ниже?

В этой лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Всюду предполагается, что в индивидуальных задачах каждый язык представлен контекстно-свободной грамматикой (но можно, конечно, использовать и автоматы с магазинной памятью).

В разделе 16.1 доказывается неразрешимость проблемы пустоты пересечения контекстно-свободных языков и проблемы бесконечности пересечения контекстно-свободных языков.

В разделе 16.2 доказывается неразрешимость проблемы однозначности контекстно-свободной грамматики.

В разделе 16.3 доказывается неразрешимость проблемы равенства контекстно-свободных языков.

В разделе 16.4 доказывается неразрешимость проблемы автоматности контекстно-свободного языка.

В разделе 16.5 доказывается неразрешимость проблем контекстной свободности дополнения контекстно-свободного языка и пересечения контекстно-свободных языков.