Genetic Algorithm for the Induction of Nondeterministic Pushdown Automata

摘要

This paper presents a genetic algorithm used to infer pushdown automata fromlegal and illegal examples of a language. It gives an introduction into grammatical inference, and discusses related work in grammatical inference using genetic algorithms. The paper describes the type of automation 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 interference 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.