Evolving pushdown automata

ABSTRACT

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.

REFERENCES

• 1: Brave S., Evolving Deterministic Finite Automata Using Cellular Encoding. In Proceedings of the First Annual Conference on Genetic Programming (GP 96), eds. J. R. Koza et al., MIT Press, 1996, pp. 39--44.
• 2: Daniel I. Cohen, Introduction to computer theory, John Wiley & Sons, Inc., New York, NY, 1986
• 3: Dunay B. D., Context Free Language Induction with Genetic Programming. In Proceedings of the 1994 International Conference on Tools with Artificial Intelligence (New Orleans, LA), IEEE Computer Society Press, 1994, pp. 828--831.
• 4: Dunay B. D., Petry F. E., Buckles B. P, Regular Language Induction with Genetic Programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, Orlando, Florida, USA, IEEE Press, pp. 396--400.
• 5: Pierre Dupont, Regular Grammatical Inference from Positive and Negative Samples by Genetic Search: the GIG Method, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.236-245, September 21-23, 1994
• 6: Lawrence J. Fogel, Intelligence through simulated evolution: forty years of evolutionary programming, John Wiley & Sons, Inc., New York, NY, 1999
• 7: Huijsen W., Genetic Grammatical Inference. In CLIN IV: Papers from the Fourth CLIN Meeting, Vakgroep, Alfa-Informatica, eds. Bouma G. and van Noord G., University of Groringeng, 1994, pp. 59--72.
• 8: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 9: Lankhorst M., A Genetic Algorithm for Induction of Nondeterministic Pushdown Automata, Computer Science Report CS-R 9502, University of Groningen, the Netherlands, 1995, http://citeseer.ist.psu.edu/lankhorst95genetic.html.
• 10: Peter Linz, An Introduction to Formal Language and Automata, Jones and Bartlett Publishers, Inc., 2006
• 11: Luke S., Hamahashi S., Kitano H., "Genetic" Programming. In Proceedings of the Genetic Programming and Evolutionary Computation Conference, in eds. W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzan, V. Honavar, M. Jakiela and R. E. Smith, Vol. 2, Orlando, Florida, USA, 1999, pp. 1098--1105.
• 12: Mahfoud S. W., Niching Methods for Genetic Algorithms, IlliGal Report No. 95001, University of Illinois at Urbana-Champaign, Urbana, IL, May 1995, http://citeseer.nj.nec.com/mahfoud95niching.html.
• 13: Zomorodian A., Context-Free Language Induction by Evolution of Deterministic Push-down Automata Using Genetic Programming. In the proceedings of the AAAI 1995 Fall Symposium, 1995, http://citeseer.ist.psu.edu/591840.html.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General

General Terms:
Algorithms, Theory

Keywords:
genetic programming, grammatical inference