Testing the Equivalence of Regular Languages

Marco Almeida
Nelma Moreira
Rogério Reis

The minimal deterministic finite automaton is generally used to

determine regular languages equality. Antimirov and Mosses proposed

a rewrite system for deciding regular expressions equivalence of

which Almeida et al. presented an improved variant. Hopcroft

and Karp proposed an almost linear algorithm for testing the

equivalence of two deterministic finite automata that avoids


In this paper we improve the best-case running time, present an

extension of this algorithm to non-deterministic finite automata,

and establish a relationship between this algorithm and the one

proposed in Almeida et al. We also present some experimental

comparative results. All these algorithms are closely related with

the recent coalgebraic approach to automata proposed by Rutten.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 47–57.
Published: 30th July 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.3.4 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org