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

Research output: Contribution to journalArticle

2 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

Personal digital assistants
Simulators
Genetic algorithms
Taguchi methods
Masks
Acoustic waves

Keywords

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

Cite this

@article{81b40cbc202e4bc4bda77567f54df995,
title = "Genetic Algorithm for Grammar Induction and Rules Verification through a PDA Simulator",
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.",
keywords = "Context free grammar, Genetic algorithm, Grammar induction, Parsing, Pushdown automata",
author = "Hari Pandey",
year = "2017",
month = "9",
day = "30",
doi = "http://doi.org/10.11591/ij-ai.v6.i3.pp100-111",
language = "English",
volume = "6",
pages = "100--111",
journal = "IAES International Journal of Artificial Intelligence",
issn = "2089-4872",
publisher = "Institute of Advanced Engineering and Science",
number = "3",

}

TY - JOUR

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

AU - Pandey, Hari

PY - 2017/9/30

Y1 - 2017/9/30

N2 - 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.

AB - 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.

KW - Context free grammar

KW - Genetic algorithm

KW - Grammar induction

KW - Parsing

KW - Pushdown automata

U2 - http://doi.org/10.11591/ij-ai.v6.i3.pp100-111

DO - http://doi.org/10.11591/ij-ai.v6.i3.pp100-111

M3 - Article

VL - 6

SP - 100

EP - 111

JO - IAES International Journal of Artificial Intelligence

JF - IAES International Journal of Artificial Intelligence

SN - 2089-4872

IS - 3

ER -