Математическая теория формальных языков

       

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


Теорема 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.

Эквивалентен ли конечный автомат

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


Содержание раздела