001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of LearnLib, http://www.learnlib.de/.
003 *
004 * LearnLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 *
008 * LearnLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 *
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with LearnLib; if not, see
015 * <http://www.gnu.de/documents/lgpl.en.html>.
016 */
017package de.learnlib.examples.example1;
018
019import java.io.IOException;
020import java.io.Writer;
021import java.util.Collections;
022
023import net.automatalib.automata.fsa.DFA;
024import net.automatalib.automata.fsa.impl.compact.CompactDFA;
025import net.automatalib.commons.dotutil.DOT;
026import net.automatalib.util.graphs.dot.GraphDOT;
027import net.automatalib.words.Alphabet;
028import net.automatalib.words.Word;
029import net.automatalib.words.impl.Alphabets;
030import de.learnlib.algorithms.lstargeneric.ce.ObservationTableCEXHandlers;
031import de.learnlib.algorithms.lstargeneric.closing.ClosingStrategies;
032import de.learnlib.algorithms.lstargeneric.dfa.ExtensibleLStarDFA;
033import de.learnlib.api.MembershipOracle.DFAMembershipOracle;
034import de.learnlib.eqtests.basic.WMethodEQOracle.DFAWMethodEQOracle;
035import de.learnlib.experiments.Experiment.DFAExperiment;
036import de.learnlib.oracles.CounterOracle.DFACounterOracle;
037import de.learnlib.oracles.SimulatorOracle.DFASimulatorOracle;
038import de.learnlib.statistics.SimpleProfiler;
039
040/**
041 * This example shows the usage of a learning algorithm and an equivalence test
042 * as part of an experiment in order to learn a simulated SUL (system under
043 * learning).
044 *
045 * @author falkhowar
046 */
047public class Example {
048
049    /**
050     * creates example from Angluin's seminal paper.
051     * 
052     * @return example dfa
053     */
054    private static CompactDFA<Character> constructSUL() {
055        // input alphabet contains characters 'a'..'b'
056        Alphabet<Character> sigma = Alphabets.characters('a', 'b');
057
058        // create states
059        CompactDFA<Character> dfa = new CompactDFA<>(sigma);
060        int q0 = dfa.addInitialState(true);
061        int q1 = dfa.addState(false);
062        int q2 = dfa.addState(false);
063        int q3 = dfa.addState(false);
064
065        // create transitions
066        dfa.addTransition(q0, 'a', q1);
067        dfa.addTransition(q0, 'b', q2);
068        dfa.addTransition(q1, 'a', q0);
069        dfa.addTransition(q1, 'b', q3);
070        dfa.addTransition(q2, 'a', q3);
071        dfa.addTransition(q2, 'b', q0);
072        dfa.addTransition(q3, 'a', q2);
073        dfa.addTransition(q3, 'b', q1);
074
075        return dfa;
076    }
077
078    public static void main(String[] args) throws IOException {
079
080        // load DFA and alphabet
081        CompactDFA<Character> target = constructSUL();
082        Alphabet<Character> inputs = target.getInputAlphabet();
083
084        // typed empty word
085        Word<Character> epsilon = Word.epsilon();
086
087        // construct a simulator membership query oracle
088        // input  - Character (determined by example)
089        DFAMembershipOracle<Character> sul = new DFASimulatorOracle<>(target);
090
091        // oracle for counting queries wraps SUL
092        DFACounterOracle<Character> mqOracle =
093                new DFACounterOracle<>(sul, "membership queries");
094
095        // construct L* instance
096        ExtensibleLStarDFA<Character> lstar = new ExtensibleLStarDFA<>(
097                inputs, // input alphabet
098                mqOracle, // mq oracle
099                Collections.singletonList(epsilon), // initial suffixes
100                ObservationTableCEXHandlers.CLASSIC_LSTAR, // handling of counterexamples
101                ClosingStrategies.CLOSE_FIRST // always choose first unclosedness found
102                );
103
104        // construct a W-method conformance test
105        // exploring the system up to depth 4 from
106        // every state of a hypothesis
107        DFAWMethodEQOracle<Character> wMethod =
108                new DFAWMethodEQOracle<>(4, mqOracle);
109
110        // construct a learning experiment from
111        // the learning algorithm and the conformance test.
112        // The experiment will execute the main loop of
113        // active learning
114        DFAExperiment<Character> experiment =
115                new DFAExperiment<>(lstar, wMethod, inputs);
116
117        // turn on time profiling
118        experiment.setProfile(true);
119
120        // enable logging of models
121        experiment.setLogModels(true);
122
123        // run experiment
124        experiment.run();
125
126        // get learned model
127        DFA<?, Character> result = experiment.getFinalHypothesis();
128
129        // report results
130        System.out.println("-------------------------------------------------------");
131
132        // profiling
133        System.out.println(SimpleProfiler.getResults());
134
135        // learning statistics
136        System.out.println(experiment.getRounds().getSummary());
137        System.out.println(mqOracle.getStatisticalData().getSummary());
138
139        // model statistics
140        System.out.println("States: " + result.size());
141        System.out.println("Sigma: " + inputs.size());
142
143        // show model
144        System.out.println();
145        System.out.println("Model: ");
146        GraphDOT.write(result, inputs, System.out); // may throw IOException!
147
148        Writer w = DOT.createDotWriter(true);
149        GraphDOT.write(result, inputs, w);
150        w.close();
151
152        System.out.println("-------------------------------------------------------");
153    }
154}