The Problem

Consider a set of input strings is given where the strings constitute of some symbols from an alphabet . The problem is to construct the DFA that defines the language and hence specify the grammar that generates . In Machine Learning (ML) sense the input strings form an example set from which a `regular grammar' is to be learned. The success of the resulting grammar can be evaluated by

• Considering the rate of acceptance in
• and the `simplicity' of the grammar.

From simplicity one understands minimal number of states, rules and transitions.

This structure of the problem makes GA a good candidate for the learning process. There exist attempts in which CFG's are approached by GBML [6]. Unfortunately, as indicated in these works the results were not very promising.