Language Quotients Revisited

Abstract

We revisit the basic concept of quotient of a regular language R by a language L that is not necessarily regular. We revise the deterministic complexity upper bounds of the quotient operation, and we also address the nondeterministic case. Specifically, the revised deterministic upper bound is shown to be more accurate for all hard streams of regular languages. When both languages R and L are regular, we give algorithms to construct their quotient in four ways. If the two languages are given via NFAs, the first algorithm produces an NFA for the desired quotient. If the two languages are given via regular expressions, we present an algorithm that produces a regular expression for the quotient both using ordinary derivatives and using partial derivatives. Finally, we consider regular expressions with a quotient operator and define the set of partial derivatives for regular expressions with this operator. Thus, using the partial derivative automaton, one can directly produce an NFA for the quotient. We have implemented all algorithms and present here experimental results.