Comparison between L* and NL* algorithm

[VishalPatel43]

I want to compare the time, membership query, equivalence query between L* and NL* some other measurement for my research work
I need some help so what input should I have to this algorithm because DFA and NFA accept the same language.

1. If L* and NL* both take same regular expression then how can we generate random regular expression
   or
2. If L* take DFA and NL* takes NFA then I have to first generate the random DFA then convert into NFA then give SUL to the NL* which might be the dot file

Generate random DFAs (which can be regular expression or the dot file of DFA)

or just give the suggestion what can I do to compare both L* and NL* with given metric and what input should be given for accept the same regular langugage?

And How to configure Learnlib for this approach?

[mtf90]

1. AutomataLib does not directly support regular expressions, but the BRICS library does. Furthermore, AutomataLib provides an adapter module that allows you to wrap BRICS automata in AutomataLib- (and LearnLib-) compatible classes (see, e.g.,. the respective test-cases for some examples). Maybe you can use the classes of the BRICS library to randomly construct regular expressions.
2. The learning algorithms only require a MembershipOracle<I, Boolean> to interact with the SUL. So it is perfectly fine to provide the L* learner with an NFA-based SUL since the membership question is still answered deterministically. However, it may happen that the hypothesis inferred by L* is exponentially larger than the one by NL* (cf. the powerset construction for determinizing NFAs). Another challenge may be the EquivalenceOracles because most testing methods in AutomataLib require deterministic automata. Here, it may be necessary to first determinize the NFA (hypothesis). However, this is a separated process that should not affect the remaining inferece process.

[VishalPatel43]

Thank you for the reply.

Still I don't understand

how to compare L* and NL* time, queries all things which the input --> I have doubt regarding inputs, what is the Oracle (SUL) for the L* and NL* algo.
What input should I provide to these algos for learning automata and how?

[mtf90]

Here is a small sketch that I put together on the current development version of LearnLib/AutomataLib:

public static void main(String[] args) {
    final Automaton sul = new RegExp("a(b*|bb+)c?d").toAutomaton();
    final Alphabet<Character> alphabet = Alphabets.characters('a', 'd');
    final BricsDFA dfa = new BricsDFA(sul, true);
    final MembershipOracle<Character, Boolean > mqo = new SimulatorOracle<>(dfa);

    final CounterOracle<Character, Boolean> lstarCounter = new CounterOracle<>(mqo);
    final CounterOracle<Character, Boolean> nlstarCounter = new CounterOracle<>(mqo);

    final ClassicLStarDFA<Character> lstar = new ClassicLStarDFA<>(alphabet, lstarCounter);
    final NLStarLearner<Character> nlstar = new NLStarLearner<>(alphabet, nlstarCounter);

    // the challenge is to find an equivalence oracle that works for DFAs and NFAs
    // here, we simply use the W-method tests based on the determinized RegExp
    final SampleSetEQOracle<Character, Boolean> eqo = new SampleSetEQOracle<>(false);
    eqo.addAll(mqo, Lists.newArrayList(new WMethodTestsIterator<>(dfa, alphabet)));

    final Experiment<DFA<?, Character>> lstarExp = new Experiment<>(lstar, eqo, alphabet);
    final Experiment<NFA<?, Character>> nlstarExp = new Experiment<>(nlstar, eqo, alphabet);

    lstarExp.run();
    nlstarExp.run();

    System.out.println("LStar");
    System.out.println(lstarCounter.getStatisticalData().getDetails());
    System.out.println("NLStar");
    System.out.println(nlstarCounter.getStatisticalData().getDetails());

    Visualization.visualize(lstarExp.getFinalHypothesis(), alphabet);
    Visualization.visualize(nlstarExp.getFinalHypothesis(), alphabet);
}

If you decide to use the BRICS library to create RegExps, you need to manually add the

<dependency>
    <groupId>dk.brics</groupId>
    <artifactId>automaton</artifactId>
</dependency>

dependency, because it is (intentionally) not resolved transitively by Maven. But you are free to use any input alphabet and SUL as long as you can provide a MembershipOracle<I, Boolean> and a proper EquivalenceOracle<A, I, Boolean> implementation.

[VishalPatel43]

Can you help me, how learnlib and automatalib library use in new project with maven like how they use in the statelearner , so I can use directly, coz I don't want to modified the learnlib code

[mtf90]

If you want the simplest configuration possible, you may add the following dependencies to your (external) project:

<dependency>
    <groupId>net.automatalib.distribution</groupId>
    <artifactId>automata-distribution</artifactId>
    <version>${automatalib.version}</version>
    <type>pom</type>
</dependency>
<dependency>
    <groupId>de.learnlib.distribution</groupId>
    <artifactId>learnlib-distribution</artifactId>
    <version>${learnlib.version}</version>
    <type>pom</type>
</dependency>

This adds all automatalib and learnlib dependencies to your project (possibly including ones that you don't really need such as other learning algorithms). If you want a more fine-grained control over the dependencies you could import the above distribution dependencies in your <dependencyManagement> (similar to how the statelearner does it) and only select individual depenencies. An overwiew of the current (stable) AutomataLib and LearnLib artifacts can be found here and here.

If you want to use the latest stable versions of AutomataLib/LearnLib (0.10.0 / 0.16.0) you are done. If you want to use the latest development versions (0.11.0-SNAPSHOT / 0.17.0-SNAPSHOT) you'll need to add the Sonatype Snapshot Repository as described, e.g., here. You may have a look at the current changelogs (here and here) if there are any changes which would require you to use the development versions. Otherwise, you should be fine with using the latest stable versions.

[mtf90]

Do you still need guidance, or can we mark this thread as resolved?