Hopcroft and Karp's algorithm for Non-deterministic Finite Automata

An algorithm is given for determining if two non-deterministic nite au- tomata are language equivalent. We exploit up-to techniques to improve the standard algorithm by Hopcroft and Karp for deterministic nite automata [10], so as to avoid computing the whole deterministic automata. Although the proposed algorithm remains exponential in worst case (the problem is PSPACE-complete), experimental results show that it can be much

faster than the standard algorithm: only a very small portion of the determinized automata have to be explored in practice. Keywords Language Equivalence, Non-deterministic Finite Automata, Bisimulation, Coinduction, Up-to techniques, Congruence. 1 Introduction Checking language equivalence of nite automata is a classical problem in com- puter science, that nds applications in many elds ranging from compilers construction to model checking. Equivalence of deterministic nite automata (DFA) can be checked either via minimization [9, 4] or through Hopcroft and Karp’s algorithm [10, 2], which exploits an instance of what is nowadays called a coinduction proof principle [13, 18, 16, 1]: two states recognise the same language if and only if there exists a bisimulation relating them. In order to check the equivalence of two given states, Hopcroft and Karp’s algorithm creates a relation containing them and tries to build a bisimulation, by adding pairs of states to this relation: if it succeeds then the two states are equivalent, otherwise they are di erent. On the one hand, minimization has the advantage of checking the equiv- alence of all the states at once (while Hopcroft and Karp only of a certain pair of the states). On the other hand, minimization has the disadvantage of ENS Lyon, Universit e de Lyon, LIP (UMR 5668) yCNRS, Universit e de Grenoble, LIG (UMR 5217) 1 hal-00639716, version 2 - 6 Dec 201 1 needing the whole automata from the beginning, while Hopcroft and Karp’s algorithm can be executed on the y" on lazy DFA, which are constructed on demand. This di erence is fundamental for our work: when starting from non-deterministic nite automata (NFA), the powerset construction used to get deterministic automata induces an exponential factor. Indeed, the algorithm we introduce in this work for checking equivalence of NFA usually" does not build the whole deterministic automaton, but just a small part of it. We write usually" because in few bad cases, the algorithm still needs exponentially many states of the DFA (otherwise we would have solved in polynomial time the problem of language equivalence, which is PSPACE- complete [12]). Our algorithm is grounded on a simple observation on determinized NFA: for all sets X and Y of states of the original NFA, the union (written +) of the language recognised by X (written [[X]]) with the language recognised by Y ([[Y]]) is equal to the language recognised by the union of X and Y...

Website: hal.archives-ouvertes.fr | Filesize: -
No of Page(s): 26
Download Hopcroft and Karp's algorithm for Non-deterministic Finite Automata.pdf