Testing Learning of Restarting Automata using Genetic Algorithm

Title: Testing the Learning of Restarting Automata using Genetic Algorithm Author: Bc. Lenka Kovářová Department: Department of Software and Computer Science Education Supervisor: RNDr. František Mráz, CSc. Abstract: Restarting automaton is a theoretical model of device recognizing a formal language. The construction of various versions of restarting automata can be a hard work. Many different methods of learning such automata have been developed till now. Among them are also methods for learning target restarting automaton from a finite set of positive and negative samples using genetic algorithms. In this work, we propose a method for improving learning of restarting automata by means of evolutionary algorithms. The improvement consists in inserting new rules of a special form enabling adaption of the learning algorithm to the particular language. Furthermore, there is proposed a system for testing of learning algorithms for restarting automata supporting especially learning by evolutionary algorithms. A part of the work is a program for learning restarting automata using the proposed new method with a subsequent testing of discovered automata and its evaluation in a graphic form mainly. Keywords: machine learning, grammatical inference, restarting automata, genetic algorithm