International Journal of Advancements in Technology
Open Access

Abstract

Developing Genetic Algorithm Library Using Java for CFG Induction

N.S. Choubey, Hari Mohan Pandey, M.U. Kharat

Grammar Induction is the process of learning grammar from training data of the positive (S+) and negative (S-) strings of the language. The paper discusses the approach to develop a library for inducing the context free grammar using Genetic Algorithms. Genetic Algorithm used for the induction library produces successive generations of individuals‟ chromosome, computes their fitness value in every step of generation and finally select the best out of the total number of generation or when the termination condition (threshold) is meet. The library also deals with the issues in implementation of the algorithm, chromosome representation, evaluation, selection and replacement strategy and the genetic operators for crossover and mutation. The paper also addresses the solution of the problem like useless production, left recursion, left factor, and unit production etc. The library has been implemented and the results obtained for the set of various problems like balanced parenthesis, two symbol palindromes and equal number of 0s and 1s are presented.