Genetic Algorithm for Grammar Induction and Rules Verification through a PDA Simulator

Research output: Contribution to journalArticle

37 Downloads (Pure)

Abstract

The focus of this paper is towards developing a grammatical inference system uses a genetic algorithm (GA), has a powerful global exploration capability that can exploit the optimum offspring. The implemented system runs in two phases: first, generation of grammar rules and verification and then applies the GA’s operation to optimize the rules. A pushdown automata simulator has been developed, which parse the training data over the grammar’s rules. An inverted mutation with random mask and then ‘XOR’ operator has been applied introduces diversity in the population, helps the GA not to get trapped at local optimum. Taguchi method has been incorporated to tune the parameters makes the proposed approach more robust, statistically sound and quickly convergent. The performance of the proposed system has been compared with: classical GA, random offspring GA and crowding algorithms. Overall, a grammatical inference system has been developed that employs a PDA simulator for verification.
Original languageEnglish
Pages (from-to)100-111
JournalIAES International Journal of Artificial Intelligence (IJ-AI)
Volume6
Issue number3
Early online date30 Sep 2017
DOIs
Publication statusE-pub ahead of print - 30 Sep 2017

    Fingerprint

Keywords

  • Context free grammar
  • Genetic algorithm
  • Grammar induction
  • Parsing
  • Pushdown automata

Cite this