On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata

Abstract

The known proofs that the equivalence and containment problems for regular expressions, regular grammars and nondeterministic finite automata are PSPACE-complete [SM] depend upon consideration of highly unambiguous expressions, grammars and automata. Here, we prove that such dependence is inherent. Deterministic polynomial-time algorithms are presented for the equivalence and containment problems for unambiguous regular expressions, unambiguous regular grammars and unambiguous finite automata. The algorithms are then extended to ambiguity bounded by a fixed k. Our algorithms depend upon several elementary observations on the solutions of systems of homogeneous linear difference equations with constant coefficients and their relationship with the number of derivations of strings of a given length n by a regular grammar.