Д. Е. Александров, А. В. Красненкова, “Практические оценки сложности регулярных выражений”, Интеллектуальные системы. Теория и приложения, 2021, том 25, выпуск 4,страницы 53

Часть 2. Математика и компьютерные науки

Практические оценки сложности регулярных выражений

Д. Е. Александров, А. В. Красненкова

МГУ

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

Ключевые слова: конечные автоматы, регулярные выражения, экспоненциальный взрыв, вычислительные эксперименты.