Evolving Finite State Transducers: Some Initial Explorations

Finite state transducers (FSTs) are finite state machines that map strings in a source domain into strings in a target domain. While there are many reports in the literature of evolving general finite state machines, there has been much less work on evolving FSTs. In particular, the fitness functions required for evolving FSTs are generally different to those used for FSMs. This paper considers three string-distance based fitness functions. We compute their fitness distance correlations, and present results on using two of these (Strict and Hamming) to evolve FSTs. We can control the difficulty of the problem by the presence of short strings in the training set, which make the learning problem easier. In the case of the harder problem, the Hamming measure performs best, while the Strict measure performs best on the easier problem.