A>Вообще задача такая. Строятся различные регулярные выражения, используя в том числе операции пересечения и вычитания. После этого нужно для заданных двух выражений определять дают ли они в пересечении пустой язык или нет.
Хороший пример PSPACE-complete задачи. Ну удачи тебе в поиске быстрого решения :)
A>Именно это я и хочу. На итоговую оценку сложности это не должно повлиять.
О какой оценке ты говоришь? Там как требовалось огромное число действий, так и будет требоваться.
