GA Representation of DFA

  In the subject problem the entity that is searched for is the DFA that will accept a known set of strings. So naturally, it is the DFA that is encoded into a chromosome. The population of chromosomes will serve as a pool of candidate DFA solutions. In GA it is most preferable to have a fixed length of chromosomes which corresponds to imposing an upperbound to the number of states in the DFA. With an appropriate choice of a penalty in the objective function the system will be forced to favor least number of states (see 3.3.1).

A DFA can be represented by a matrix where the states enumerate the rows and the possible tokens enumerate the columns.

is the start state. The following definition of completes the representation of DFA without any loss of generality.

The GA representation is the mapping of the elements of this matrix onto a chromosome that constitutes of genes by the equation:

In the implementation the chromosome has been chosen to be a vector of single-byte integers. Furthermore,

• is represented using the natural number k itself,
• is represented by 0,
• is represented by the integer -1.

So, in particular the example of the small DFA of section 1 would have a GA data representation of