Как всем известно, регулярные выражения с точки зрения теории формальных языков задаются через символы языка и операторы конкатенации, объединения и повторения. Поскольку регулярные языки (задаваемые регулярными выражениями) замкнуты не только относительно данных операций, но ещё и относительно операций дополнения, вычитания и пересечения, расширим регулярные выражения так, чтобы их можно было задавать через операторы
— конкатенация
— объединение
— повторение
— дополнение
— вычитание
— пересечение
— обращение

Хочется иметь алгоритм, который будет
— эффективно (значит быстро работать на практике*) строить по данному расширенному выражению детерминированный конечный автомат.
— вычислять является ли пустым язык, задаваемый расширенным регулярным выражением.

*Вообще, можно на каждое подвыражение строить автоматы, и выполнять операции над ними, но это медленно.

Интересует литература, где бы это могло быть описано. В "классических" книгах описаны только доказательства того, что класс регулярных языков замкнут относительно этих операций. Мне же нужны эффективные алгоритмы, а не доказательства.

ДКА можно строить из регулярно выражения путем построения промежуточного НКА. Как нужно расширить НКА для того чтобы получать его из расширенного операциями (дополнение, вычитание, пересечение) регулярного выражения за линейное время? Видимо нужны какие то дополнительные типы переходов между состояниями.