How do you implement a simple SUL for a DFA?

[raufum]

I have a certain DFA in mind of which I know the accept condition, but I dont explicitly know how the DFA looks like.

The alphabet of the DFA is {0,1} and a word should be accepted if and only if its decimal representation is divisable by 3 for example (but it can also be any other number other than 3)

Can you give me the code where the SUL instance is defined and the SUL is then learned with a learning algorithm?

[mtf90]

Most (DFA-based) learning algorithms only require a MembershipOracle<I, Boolean> to interact with the system under learning. To make things easier in the beginning (especially if you don't care about parallelization), you can also implement the SingleQueryOracle<I, Boolean> interface instead.

This interface requires you to return for a prefix and suffix whether the concatenated word is accepted by your system. Here, you can implement you system logic (e.g., whether the binary representation is divisable by 3).

For setting up the rest of the learning process, you can have a look at the examples and simply replace the oracles with your own implementation.

If you have further questions, feel free to ask.

[raufum]

Hey thank you so much, I could implement my desired SUL (see picture below) - but I have some follow up question:

1. Can you give me examples where Automata Learning is actually used to infer a DFA - I could only find examples where Mealy Machines are used?
2. Can you give me a benchmarking source for realistic DFAs, that model real life systems (so a set of DFAs that I can use for experiments as a means of comparison)?
3. What kind of methods/techniques are there (implemented in LearnLib) if information of the SUL is known, so that the amount of membership queries can be reduced for example? What kind of information about the SUL is helpful to know?
4. A theoretical question: Can you give me references where the worst case complexity for the membership queries is realized for the different algorithms (L*, RivestShapire, KearnsVazirani, ObservationPack...) (i.e. a family of languages so given the specification of the algorithm the computation is equal to the worst case) - this would also be helpful for comparisons to the average case for real-life systems/random systems

You dont have to answer all these questions explicitly, just giving me some references would be very helpful!

[mtf90]

1. I can't think of any major DFA-based systems from the top of my head (except for some benchmarks, see 2.). The problem with DFAs is that they have very poor distinguishing power. Let's say you have a 3-letter input word. A DFA can only distinguish between an accepting and a rejecting behavior. A Mealy machine (even with only a binary output alphabet) could distinguish between up to 2^3 = 8 behaviors. So as soon as you have some kind of recording/tracing mechanism, Mealy machines (or Moore machines) are often much more preferable due to their higher effectiveness. Given that many software/hardware systems nowadays allow for such observations, you have this concentration on reactive systems. Maybe you are lucky with some older papers/benchmarks, where Mealy machine learning wasn't that prominent yet. Alternatively, you can always interpret Mealy machines as DFAs (e.g., via alternating or synchronous intput/output symbols) if you want to enforce a common base formalism.
2. I know of the CADP Toolbox which has been used to generate some DFA benchmarks in LearnLib. Furthermore there exist some community efforts to collect benchmarks for automata learning, but you have a surplus of Mealy machines there as well. Maybe you are lucky with some of the more advanced challenges such as RERS which do not directly target DFA learning, but whose systems may be usable for this purpose.
3. The equivalence-oracle module holds all the equivalence checks of LearnLib. Especially if you have an upper bound on the number of states of the SUL, approaches such as the W-method or the partial W-method (WpMethod) can be used to guarantee a complete and correct verification of the SUL. The randomized versions have shown some improved performance in practice. If you don't have any additional knowledge about the SUL, you could still try to use these methods approximately or fall back to heuristics such as random words.
4. Probably a good starting point would be the papers of the respective learning algorithms because the authors would have to argue why their learners have the denoted query complexity. If I remember correctly, Dana Angluin later also wrote some papers about general computational learning theory which show some hard bounds. One problem that is hard for DFAs is counting (e.g., a language that only contains words with multiples of 5 a's). The automata typically degenerate into a list-like form and you need n-1 distinguishing futures to separate all states ("a" separates the accepting state from its predecessor, "aa" distinguishes the accepting state from its pre-predecessor, and so on). I don't know if they actually hit the worst-case bound, but they are rather unpleasant to learn.