Evolving Finite Acceptors for Regular Languages

Abstract. Finite state machines play a key role in domains such as networking and natural language processing. Efforts are being directed at identifying methodologies to induce finite acceptors for a language given a subset of positive and negative sentences of the language. The study presented in this paper evaluates evolutionary algorithms (EAs) for the induction of finite acceptors for regular languages. This study differs from previous work employing evolutionary algorithms for this purpose in that each automaton is directly represented and evolved. In addition to this the study examines the evolution of both deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs), whereas previous studies have concentrated on DFAs only. The EA implemented was able to evolve both DFAs and NFAs for a set of fifteen benchmark languages. In a number of cases the minimal DFA or NFA was induced. Furthermore, the performance of this evolutionary algorithm employing a direct representation of automata has performed comparably to other evolutionary methodologies on the set of benchmarks