Study and implementation of regular grammar inference algorithms.

number: 
603
إنجليزية
department: 
Degree: 
Imprint: 
Computer Science
Author: 
Ala'a A. Hamed Al-Obaidy
Supervisor: 
Dr. Taha Saddon
year: 
2002
Abstract:

The grammatical inference is described as an instance of the inductive learning problem which can be formulated as the task of discovering common structures in examples which are supposed to be generated by the same process. In particular case, the examples are structures defined on a specific alphabet and the common structures are presented by a grammar or an equivalent machine. Once the grammar has been inferred from the learning data, the induced language is defined. The learning data may include a set of negative information, not representing the common structure, may also help in the language inductive process. This work is limited to one of the important type of formal languages, that is the regular language, which have many areas of applications. Six regular inference methods and algorithms are implemented and studied (some time after a little modification or suasestion of modification), associated with a proposed approach based on genetic algorithm. Comparison was made between these methods, using the resulting induced grammar and equivalently a minimized deterministic finite state automaton, and for more clarity regular expression also obtained and presented. It is seen that many algorithms failed to obtain reasonable grammar especially when the sample set is of complex structure, and some other alternate in there results. The proposed genetic approach gives reasonable results but its induced a complicated grammar with a very large size deterministic finite state automaton, when the sample size is large and of long word lengths. A suit of programs has been designed on seven selected algorithms, using Delphi ver. 5 programming language.