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

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

A>>ДКА можно строить из регулярно выражения путем построения промежуточного НКА.
W>Есть хорошие алгоритмы по построению ДКА по регулярному выражению и без этого шага.

A>>Как нужно расширить НКА для того чтобы получать его из расширенного операциями (дополнение, вычитание, пересечение) регулярного выражения за линейное время?
W>За линейное время от чего?
W>Если у тебя есть автоматы с числом состояний m и n для двух каких-то регулярных выражений, то автомат, принимающий пересечение соответствующих языков, может иметь mn состояний. В качестве примера можно рассмотреть пару РВ: (aaaa)* и (aaaaa)*, у которой в результате пересечения получиться длинное РВ (aaaaaaaaaaaaaaaaaaaa)* с автоматом, у которого также будет много состояний.
W>То есть твои расширенные регулярные выражения могут приводить к комбинаторному взрыву. Получается, что алгоритма построения ДКА/НКА с линейным от размера входа временем работы не существует, ибо сам размер выходного автомата велик.
Алгоритма построения ДКА разумеется не существует.
W>Разумеется, ты можешь сделать расширенный-НКА чтобы уметь делать то же пересечение быстро. Но это лишь откладывание проблемы на потом, ибо расширенный-НКА в ДКА придётся преобразовывать другим алгоритмом, который всё также будет вынужден иметь дело с огромным числом состояний (которых будет куда больше чем при преобразовании обычного НКА в ДКА).
Именно это я и хочу. На итоговую оценку сложности это не должно повлиять. Дело в том, что если я буду создавать конечный автомат для каждого подвыражения и объединять сами автоматы (заданные стандартным образом), для каждой операции пересечения нужно будет полностью перестраивать автомат. При реализации этого на языке программирования, будет много выделений памяти.

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