State of the art on grammatical inference using evolutionary method


*Corresponding author for this work

Research output: Book/ReportBookpeer-review



State of the Art on Grammatical Inference Using Evolutionary Method presents an approach for grammatical inference (GI) using evolutionary algorithms. Grammatical inference deals with the standard learning procedure to acquire grammars based on evidence about the language. It has been extensively studied due to its high importance in various fields of engineering and science. The book's prime purpose is to enhance the current state-of-the-art of grammatical inference methods and present new evolutionary algorithms-based approaches for context free grammar induction. The book's focus lies in the development of robust genetic algorithms for context free grammar induction.

The new algorithms discussed in this book incorporate Boolean-based operators during offspring generation within the execution of the genetic algorithm. Hence, the user has no limitation on utilizing the evolutionary methods for grammatical inference.

Key Features

a. Discusses and summarizes the latest developments in Grammatical Inference, with a focus on Evolutionary Methods
b. Provides an understanding of premature convergence as well as genetic algorithms
c. Presents a performance analysis of genetic algorithms as well as a complete look into the wide range of applications of
Grammatical Inference methods
d. Demonstrates how to develop a robust experimental environment to conduct experiments using evolutionary methods and algorithms

Chapter wise abstract

Chapter-1 (Introduction and Scientific Goals): This chapter presents an introductory text with motivation and scope of the present book. I have shown the research problems and main contributions. It gives a brief about grammatical inference and its effectiveness across domains. The basics of formal grammars and various existing grammatical inference methods are discussed in Chapter-2.

Chapter-2 (State of the Art: Grammatical Inference): This chapter presents the current state of the art in the context of grammatical inference methods. I have divided this chapter into two parts. Part-1 covers some of the preliminary definitions such as Backus Naur Form, grammars, Chomsky hierarchy and others. The focus of Part-2 is mainly on the different grammatical inference methods. I have presented a comprehensive discussion of each method with their strengths and weaknesses. The grammatical inference methods have been classified based on the various factors and the learning technique. At the end, I have presented challenges with grammatical inference methods and a summary.

Chapter-3 (State of the Art: Genetic Algorithms and Premature Convergence): The purpose of this chapter is to discuss genetic algorithm, which is a popular algorithm of evolutionary algorithm’s family. I have presented introduction of genetic algorithm with factors affecting its behaviour with theoretical frameworks. In addition, the challenges with the execution of genetic algorithm is presented. A state-of-art in the context of premature convergence within genetic algorithm is presented in a comprehensive manner. A detailed summary and analysis of different existing methods is given for the quick review. A comparative analysis is made available based on different parameters. The underlying motivation for this chapter is to identify methods that allow the development of new strategies to prevent premature convergence and, then apply the evolutionary algorithms for solving grammatical inference problem.

Chapter-4 (Genetic Algorithms and Grammatical Inference): The focus of this chapter is towards Evolutionary algorithms used for Grammatical Inference. For this book, I have considered Genetic Algorithms such as Bit-Masking Oriented Genetic Algorithm (BMOGA). I discuss the role of bit masking oriented data structure (BMODS) and its formation. The role of crossover mask (CM) and mutation mask (MM) are also shown with three crossover operators and a mutation mask operator. In addition, the role of Boolean based procedure is discussed with examples for the offspring generation. Lastly, algorithms are shown which uses the CM and MM with Boolean based procedure for the GI. A detailed flowchart is presented which highlights the applicability of minimum description length (MDL) principle.

Chapter-5 (Performance Analysis of Genetic Algorithm for Grammatical Inference): The primary aim of this chapter is to report the computational and statistical test results by implementing algorithms discussed in chapter-4. In this chapter, I have shown the detailed method to develop a robust experimental setup to conduct the experiments. This chapter is also dedicated to present the comparative comparison and analysis with other algorithms.

Chapter-6 (Applications of Grammatical Inference Methods and Future Development): This chapter discusses the wide range of applications of grammatical inference methods and possibilities of future investigation in this area.
Original languageEnglish
Number of pages230
ISBN (Electronic)978-0-12-822116-7
ISBN (Print) K1643252321547
Publication statusPublished - 20 Nov 2020


  • Formal Language Theory
  • Evolutionary algorithm
  • Genetic Algorithm
  • Context free grammar
  • Natural language processing
  • Optimization
  • Premature convergence
  • Convergence Analysis


Dive into the research topics of 'State of the art on grammatical inference using evolutionary method'. Together they form a unique fingerprint.

Cite this