Об оценках мощности некоторых классов регулярных языков

Рассмотрен метод модификации регулярных выражений для решения проблемы “экспоненциального взрыва” числа состояний конечного автомата, распознающего множество регулярных языков, задаваемых объединением регулярных выражений вида $.{*}$R$_1.{*}$R$_2.{*}$, где R$_1$ и R$_2$ — произвольные регулярные выражения. Приведены оценки функций роста регулярных выражений из некоторого подкласса указанного класса выражений. Предложен способ оценки относительного роста числа слов регулярного языка, задаваемого парой регулярных выражений, при модификации этих выражений. Проанализирована практическая эффективность данного метода модификации выражений и предложенного способа оценки применительно к регулярным выражениям системы Snort.