Quotient Complexity of Regular Languages
Janusz Brzozowski · 2009
The past research on the state complexity of operations on regular languages is examined, and a new approach based on an old method (derivatives of regular expressions) is presented. Since state complexity is a property of a language, it is appropriate to define it in formal-language terms as the number of distinct left quotients of the language, and to call it "quotient complexity". Suppose f is a binary regular operation (for example, union or concatenation) and g, a unary regular operation (for example, star or reversal). Moreover, let K (respectively, L) range over all regular languages with quotient complexity m (respectively, n). We want to find the worst-case quotient complexity of f(K, L) as a function of m and n, or that of g(L) as a function of n. Since quotients can be represented by derivatives, one can find a formula for the typical quotient of f(K, L) or g(L) in terms of the quotients of K and L. To obtain an upper bound on the number of quotients of f(K, L) or g(L) all one has to do is count how many such quotients are possible, and this usually makes automaton constructions unnecessary. The advantages of this point of view are illustrated by many examples. Moreover, new general observations are presented to help in the estimation of upper bounds on quotient complexity of regular operations.