Title :
A genetic algorithm for the induction of pushdown automata
Author :
Lankhors, Marc M.
Author_Institution :
Dept. of Comput. Sci., Groningen Univ., Netherlands
fDate :
29 Nov-1 Dec 1995
Abstract :
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
Keywords :
finite automata; formal languages; genetic algorithms; inference mechanisms; natural languages; pushdown automata; correctly balanced nested parentheses expressions; fitness evaluation; genetic algorithm; genetic operators; illegal language examples; inductive inference; legal language examples; natural language subset; pushdown automata; regular languages; sentences; two-symbol palindromes; Automata; Genetic algorithms; Gold; Inference algorithms; Law; Legal factors; Natural languages; Personal digital assistants; Speech analysis; Testing;
Conference_Titel :
Evolutionary Computation, 1995., IEEE International Conference on
Conference_Location :
Perth, WA
Print_ISBN :
0-7803-2759-4
DOI :
10.1109/ICEC.1995.487478
