The minimal deterministic finite automaton is generally used to determine regular languages equality. Antimirov and Mosses proposed a rewrite system for deciding reg- ular 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 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. 1 Introduction The uniqueness of the minimal deterministic finite automaton for each regular language is in general used for determining regular languages equality. Whether the languages are rep- resented by deterministic finite automata (DFA), non deterministic finite automata (NFA), or regular expressions (r.e.), the usual procedure uses the equivalent minimal DFA to decide equivalence. The best known algorithm, in terms of worst-case analysis, for DFA minimisa- tion is loglinear [Hop71], and the equivalence problem is PSPACE-complete for both NFA and r.e. Based on the algebraic properties of regular expressions, Antimirov and Mosses proposed a terminating and...
Website: www.fc.up.pt | Filesize: -
No of Page(s): 17
Download Testing the Equivalence of Regular Languages.pdf
No comments:
Post a Comment