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

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

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