A genetic algorithm for the induction of pushdown automata

Presents a genetic algorithm used to infer pushdown automata from legal and illegal examples of a language. It describes the type of automaton that is used, the evaluation of the fitness of automata with respect to a set of examples of a language, the representation of automata in the genetic algorithm, and the genetic operators that work on this representation. Results are reported on the inference of a test suite of 10 languages. Pushdown automata for the language of correctly balanced and nested parentheses expressions, the language of sentences containing an equal number of a's and b's, the two-symbol palindromes, a set of regular languages and a small natural language subset were inferred. Furthermore, some possible improvements and extensions of the algorithm are discussed