On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata

The known proofs that the equivalence and containment problems for the regular and for the linear context-free grammars are PSPACE-complete and undecidable, respecitvely, depend upon consideration of ambiguous grammars. We prove that this dependence is inherent. Deterministic polynomial time algorithms are presented for; (1) the equivalence and containment problems for the unambiguous regular grammars; (2) for all k ≥ 2, the equivalence and containment problems for the regular grammars of degree of ambiguity ≤ k; and (3) the problems of determining if an unambiguous linear context-free grammar is equivalent to or contains an arbitrary regular set. Simple extensions of the grammar classes in (1), (2), and (3) are shown to yield problems that are NP-hard or undecidable. Several new results on the relative economy of description of ambiguous versus unambiguous regular and linear contextfree grammars are also obtained. These results depend upon several observations on the solutions of systems of homogeneous linear difference equations and their relationship with the number of strings of a given length generated by an unambiguous regular or linear context-free grammar.