Математическая теория формальных языков
Проблема неравенства регулярных выражений без итерации
Теорема 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.
При этом i- й сомножитель соответствует пропозициональной переменной xi
и выбирается следующим образом:
если данная элементарная дизъюнкция не содержит ни литерала xi, ни литерала , то используем выражение (a+b);
если она содержит литерал xi, но не содержит литерала , то используем выражение a;
если она содержит литерал , но не содержит литерала xi, то используем выражение b;
если она содержит оба литерала xi и , то используем выражение 0.
Если m > 1, то построим по указанному методу для каждой из булевых формул C1, C2, ..., Cm
регулярное выражение и возьмем их сумму.
Легко видеть, что два построенных так регулярных выражения равны тогда и только тогда, когда булева формула
невыполнима.
Пример 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.
Эквивалентен ли конечный автомат
конечному автомату, изображенному ниже?
