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

Теорема 15.9.1.

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

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

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

Пусть дана булева формула , составленная из пропозициональных переменных x1, x2, ..., xn

(при более формальном подходе можно считать xi обозначением слова p#i, как это сделано в примере 7.2.8). Здесь для каждого

формула Cj

является элементарной дизъюнкцией. Для краткости будем обозначать отрицание переменной xi

через

(а не через , как в примере 7.2.8).

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

Для удобства отождествим истинностные значения "ложь" и "истина" с символами a и b соответственно. Тогда оценку пропозициональных переменных x1, x2, ..., xn

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

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

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий