Using genetic programming to evolve heuristics for DFA learning

Abstract

Inferring a grammar from a set of strings pertaining to a language is a fundamental problem in computer science. Simply finding a consistent grammar is not a difficult task. For example in the case of Deterministic Finite-State Automatons (DFA), which can be used to recognise regular languages, constructing a Prefix Tree Acceptor (PTA) from the strings that are accepted by the language, is enough of a separator for accepting and rejecting strings. However the fundamental problem lies within finding the smallest consistent grammar. As stated by Gold [green1] and Angluin [green2], finding the exact minimum DFA from a set of positive and negative set of strings is an NP-complete problem. There are two main approaches to infer a DFA from a given training set. One approach is using algorithms to find the exact minimum state DFA. These methods tend to be quite complex given that this problem is NP-complete. The other approach, which is considered more practical given its polynomial time complexity, is using state merging heuristics. These heuristics infer a DFA by greedily merging states within an initial hypothesis generated from the training set. This project aims to show whether it is possible to find heuristics capable of learning the minimum state DFA consistent with the training set, through the use of genetic programming. Furthermore, it was considered whether combining these heuristics as an ensemble will be capable of improving upon the current state of the art heuristic. The system presented in this project is split into two parts. First a genetic program inspired by Ricardo Poli’s TinyGP is outlined. This handled the evolution of heuristics and selection of the best ones from multiple runs of the program. The next part deals with the verification of these heuristics, and presents which ones are similar, or were outliers during evolution. The genetic program on its own manages to generate heuristics that are as good if not slightly better than preexisting heuristics. For comparisons, Price’s Evidence Driven State Merging (EDSM) heuristic was used as a benchmark during evolution. After verification, results showed that using this system as is, was capable of improving upon EDSM by 19.15%, using an ensemble of generated heuristics. This comparison was done on the basis of finding a minimum state DFA that is > 99% consistent with the training set.