Evolving Deterministic Finite Automata Using Cellular Encoding
Scott Brave · The MIT Press eBooks · 1996
This paper presents a method for the evolution of deterministic finite automata that combines genetic programming and cellular encoding. Programs are evolved that specify actions for the incremental growth of a deterministic finite automata from an initial single-state zygote. The results show that, given a test bed of positive and negative samples, the proposed method is successful at inducing automata to recognize several different languages. 1. Introduction The automatic creation of finite automata has long been a goal of the evolutionary computation community. Fogel et. al. [1966] was the first to propose the generation of deterministic finite automata (DFAs) by means of an evolutionary process, and the possibility of inferring languages from examples was initially established by Gold [1967]. Since then, much work has been done in the induction of DFAs for language recognition. Tomita [1982] showed that hill-climbing in the space of nine-state automata was both successful and supe...