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

Pandey, Hari (2017) Genetic Algorithm for Grammar Induction and Rules Verification through a PDA Simulator. IAES International Journal of Artificial Intelligence (IJ-AI), 6 (3). pp. 100-111. ISSN 2252-8938 DOI

Paper1212.pdf - Published Version
Available under License Creative Commons Attribution.

Download (323kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: Context free grammar, Genetic algorithm, Grammar induction, Parsing, Pushdown automata
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Computing and Information Systems
Date Deposited: 31 Oct 2018 13:14

Archive staff only

Item control page Item control page