|
Technical Report: DCC-2009-01
Testing the Equivalence of Regular Languages
Marco Almeida and Nelma Moreira and Rogério Reis
DCC-FC&LIACC, Universidade do Porto
R. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal
Phone: +351 220402919 , Fax: 351 22 402 950
E-mail: {mfa,nam,rvr}@ncc.up.pt
June 2009
Abstract
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
minimisation.
In this paper we improve the best-case running time, present an
extension of this algorithm to non-deterministic finite automaton,
and establish a relationship between this algorithm and the one
proposed in Almeida {\em 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.
|