Automata Learning (Basic)
To start learning behavioral models, it's useful to know a bit more about the techniques behind it. The learning setups HermieLab generates make use of a technique called automata learning. In this wiki, we will only summarise the basic concepts; a more detailed explanation and discussion can be found in [1].
In Automata Learning, models of a target system, often called a SUL (System Under Learning) are created by active interaction with them and reasoning about the observed output. This is done by constructing queries, which are sequences of input symbols from an input alphabet that represents the actions executable on the SUL, and answering these queries by means of actual execution. [2]
Above an example SUL is shown. We have a small GUI-Program with one button and a circle which can change color. The program can be started by calling it's 'main()' function. When the program starts, the circle is red. Whenever the user presses the button a 'press()' function is called, turning the circle green. If the user then drags the button a 'drag()' function is called which paints the circle yellow. When the user releases the button, a 'release()' function is called, painting the circle red. The program contains a 'reset()' function which can reset the program.
To perform a learning experiment a learning setup is required. Learning setup generally consists of 2 components: a Learner and a Teacher.
The Leaner questions the Teacher and reasons about the observed output. The Teacher answers the queries of the Learner. The Teacher is either the SUL itself or, more often, an adapter to the SUL. This is because in general, a SUL has no interface to apply the queries. After each query, the program should reset to its original state so that all queries are equivalent, otherwise said the queries must be independent. (Very important, this is the cause of many "bugs").
If we take our example SUL again, this means that we have 2 things. First, we have a Learner who will generate queries based on some learning algorithm. Secondly, we have a Teacher which can fire the 'start()', 'press()', 'drag()', 'release()' and 'reset()' functions of the GUI-Program and which can observe the color of the circle. When we want to learn a model of the SUL, the Learner will generate queries consisting of 'press()', 'release()' and 'drag()' to get an idea how the SUL works. The Teacher will be given these queries and execute the functions contained in this query. When he has executed all the functions in a query it gets the color of the circle, reports it back the Learner and resets the SUL. When the Learner thinks it has successfully learned the model, it performs a 'check' with the teacher who will either confirm he has correctly learned the SUL or it will give him a counterexample showing why the model is wrong and the Learner. When this happens will continue the learning process (More about this 'check' is explained in Advanced).
//TODO: Image of a Mealy Machine and DFA of the example System.
The learned models are Finite State Machines (FSMs). Currently, HermieLab supports learning 2 kinds of FSMs, namely Deterministic Finite Automatons (DFAs) and Mealy Machines. Finite State Machines have been around even before the inception of software engineering. [Y] Using finite state models in the design and testing of software and hardware has been long established and is considered a standard practice today. A good example of a model based test tool is GraphWalker, a tool used by Spotify to test it's desktop and web player. A lot has been written on FSMs, instead of explaining everything here I suggest you check out X, Y or Z.