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}