A Python DFA learning toolkit

Abstract

Deterministic Finite‐State Automata (DFA) are computational machines, that are able to accept or reject words depending on whether they belong to the target regular language that they represent. DFA learning is typically formatted, as the task of learning the smallest DFA from a training set of strings that do belong and do not belong to the regular language. A DFA learning toolkit, called DfaGo, implemented in the Go programming language, provides many data structures, tools, and state‐merging learning algorithms. However, other approaches to this learning task are not found inside of this toolkit. This is mainly due to the fact, that it would be rather inefficient to re‐implement algorithms in Go, when they can be found in other programming languages such as Python. As Python has a large number of third party packages, like keras, pytorch and AALpy, that either provide learning algorithms or methods to create complex concepts, take neural networks for example, relatively easily. The aim of this project is to create an interface between these two languages. This would either allow the DfaGo toolkit to be extended using Python or create a DFA learning module in Python using Go. Though, the interface must not sacrifice too much performance, and have the capability of handling different types of approaches to learning algorithms. With regards to testing the interface, Angluin’s L* algorithm, which is an active learning algorithm, was implemented inside of the three environments, Go, Python, and the two languages communicating together with the bridge/interface, and comparing the performance of the three runs to each other to determine the efficiency of the interface. Lastly, an RPNI implementation was used to test if sending training datasets from one language to another worked as intended. We explored three different possible solutions to be able to communicate between the two languages. The first was to call Go functions from Python. This would create a DFA learning toolkit in Go while avoiding running Python code due to its slowness in execution. However, this approach was quickly disregarded, as it required for DfaGo to be re‐written using special data types instead of native Go variables. The second and third solutions, worked by calling Python code from Go instead. The first of these two methods, used bindings to have a concurrent Python interpreter running alongside Go. While this was efficient and could work for non‐communication intensive algorithms as will be seen in the RPNI tests. For a communication intensive algorithm such as L*, it proved to not work as intended as memory addresses were not being updated and the same query was being asked. Therefore, the other solution was to use a TCP server, hosted in Go, that is able to handle queries where the learning algorithm, implemented in Python, can ask queries to. Though this worked, the performance cost of such an interface is too significant and can not be used when learning larger DFAs. This server interface was around a hundred times slower than a Go only implementation, though with the RPNI tests using the bindings to send the training dataset from Go to Python showed that this interface only increased the time by 0.1 seconds. Ultimately showing that passive learning algorithms that only require a training dataset do not inflict such a heavy toll on the performance of the algorithm.