A GENETIC APPROACH TO EVOLVE FINITE STATE AUTOMATA

Abstract

Finite-state automata are one of the most pervasive models of computation, not only theoretically, but also in all of its applications to real-life problems such as natural and formal language processing, pattern recognition, control, etc. Automatically inferring finite automata from sets of positive and negative data samples has been an important problem in computer science and many schemes have been proposed for its solution. The previous works in the evolution of finite state automata were limited to the evolution of strictly non-modular FSA. In this dissertation, a modular architecture to develop FSA accepting a particular regular language is proposed and a genetic programming procedure for evolving such structures is presented. The results on the Tomita Language benchmark indicate that the proposed procedure is able to evolve an NFA with less number of generations explored and lesser amount of time taken than the earlier non-modular evolution. ii