A New Algorithm for Determining the Equivalence of Two Finite-State Automata

Abstract

Finite-state automaton is a machine that processes input strings and produces output indicating whether the input string is accepted or not. It is an acceptor recognizer for input specification. A finite-state automaton is an input/output device that accepts strings as input and produces binary numbers 0s and 1s. Two automata are equivalent if they generate the same or similar output for each input string. That is to say, two automata are equivalent if and only if they have the same computing powers. In this paper, we develop an algorithm that can be used to determine if two automata are equivalent. Such automaton could be an non-deterministic finite automata (NFA) that is converted to deterministic finite automata (DFA) or a DFA that is minimized into another DFA (minimized DFA) which are equivalent in the sense that they have the same computing power and can therefore be used to compute the same regular expression. Examples of the use of the algorithms are provided and their results show that they are equivalent in all respects. From the examples, it is clearly seen that each pair of automaton accept the same language, hence they are said to be equivalent. The proposed algorithm performs better in terms of time and space complexities when compared with existing algorithms because it runs faster and occupies less space in the computer’s memory.