Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, Aleх, Вы писали:


A>>Вообще задача такая. Строятся различные регулярные выражения, используя в том числе операции пересечения и вычитания. После этого нужно для заданных двух выражений определять дают ли они в пересечении пустой язык или нет.
W>Хороший пример PSPACE-complete задачи. Ну удачи тебе в поиске быстрого решения
Под поиском быстрого решения я имею ввиду быстрый на практике алгоритм. Понятно, что даже построение Детерминированного конечного автомата имеет сложность O(2^n). При этом для регулярных выражений, используемых на практике, время построения обычно не достигает теоретической оценки.

A>>Именно это я и хочу. На итоговую оценку сложности это не должно повлиять.
W>О какой оценке ты говоришь? Там как требовалось огромное число действий, так и будет требоваться.
Я говорю о том, что на теоретическую оценку не повлияет, если каждый символ превратить в тривиальный конечный автомат и выполнять операции объединения, пересечения и конкатенации над автоматами, либо же строить результирующий автомат сразу по регулярному выражению. Кажется, что второй способ быстрее на практике.