Context-Free Language Induction by Evolution of Deterministic Push-Down Automata Using Genetic Programming

Afra Zomorodian

The process of learning often consists of Inductive Inference, making generalizations from samples. The problem here is finding generalizations (Grammars) for Formal Languages from finite sets of positive and negative sample sentences. The focus of this paper is on Context-Free Languages (CFL’s) as defined Context-Free Grammars (CFG’s), some of which are accepted by Deterministic Push-Down Automata (D-PDA). This paper describes a meta-language for constructing D-PDA’s. This language is then combined with Genetic Programming to evolve D-PDA’s which accept languages. The technique is illustrated with two favorite CFL’s.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.