Evolving pushdown automata
Amashini Naidoo, Nelishia Pillay · 2007
The research presented in this paper evaluates genetic programming (GP) as a means of evolving pushdown automata. Each pushdown automaton is represented as a directed graph. Tournament selection is used to select parents during each generation and the reproduction, crossover and mutation operators are applied to the chosen parents to create the next generation. The GP system was tested on a set of ten context-free languages. The system was able to induce deterministic and nondeterministic pushdown automata for the ten languages. The solutions evolved by the system are compared to "human" generated solutions and the overall performance of the approach is compared to that of evolutionary algorithms previously employed for the induction of pushdown automata.