Cardinality estimates for some classes of regular languages

We consider a method that modifies regular expressions in order to solve the “exponential explosion” problem on the number of states of the finite automaton that recognizes a set of regular languages defined by the union of regular expressions of the form $.{*}$R$_1.{*}$R$_2.{*}$, where R$_1$ and R$_2$ are arbitrary regular expressions. We estimate the growth functions of regular languages from a subclass of the described class of regular languages and propose a method for estimation of relative growth of the number of words for the modification of a language defined by a pair of regular expressions. We also analyse practical efficiency of the proposed modification method and estimation method for the case of regular expressions from the system Snort.