Abstract:
We compare the complexity of specifying a regular event by a finite automaton and a generalized regular expression. The measure of complexity of the automaton is the number of its states $G$, and the measure of complexity of the generalized regular expression is its refined length $\alpha$. We show that for generalized (having operations of set-theoretic complementation and intersection) regular expressions in a one-letter alphabet, $G\leqslant 3^\alpha$.