Conclusion

We conclude the following:

GA technique has been successful in discovering DFA.

Hence it is possible to discover a regular grammar for a given language (if it exists).

The `fitness function' serves multi-purpose optimizations well.

In this work the fitness function is used for

• seeking an accepting DFA,
• forcing minimization of the number of transitions in the DFA,
• forcing removal of looping transitions.

The result was observed to be very satisfactory.

Providing only positive examples leads to a discovery of a `more

generous' grammar. It is observed that although a success of 100% acceptance of the testbed is achieved the grammar `discovered' will generate additional strings which would not be accepted by the grammar that is used in the generation of the testbed. This is by no means an indications of a weakness of the method. Being exposed to the same example strings (from the testbed) a human intelligence would presumably infer the some similar `generous' grammar. The key point here is the need for negative examples. Examples of strings that shall be rejected by the `discovered' DFA. Although this would enhence the learning, it is considered as a cheap method which beats the purpose. If such a clear cut knowledge of what is correct, what is wrong is to hand, presumably the rules are already known. Furthermore, positive examples are practically of infinite amount if all the written corpus knowledge is considered. No such knowledge is present in a corpus form regarding the negative cases. Gathering it would need consulting a native speaker.