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.algorithms.lstargeneric.mealy; 018 019import java.util.ArrayList; 020import java.util.Collections; 021import java.util.List; 022 023import net.automatalib.automata.concepts.SuffixOutput; 024import net.automatalib.automata.transout.MealyMachine; 025import net.automatalib.automata.transout.MutableMealyMachine; 026import net.automatalib.automata.transout.impl.compact.CompactMealy; 027import net.automatalib.automata.transout.impl.compact.CompactMealyTransition; 028import net.automatalib.words.Alphabet; 029import net.automatalib.words.Word; 030import de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar; 031import de.learnlib.algorithms.lstargeneric.ce.ObservationTableCEXHandler; 032import de.learnlib.algorithms.lstargeneric.closing.ClosingStrategy; 033import de.learnlib.algorithms.lstargeneric.table.Row; 034import de.learnlib.api.MembershipOracle; 035import de.learnlib.mealy.MealyUtil; 036 037/** 038 * An implementation of the L*Mealy algorithm for inferring Mealy machines, as described 039 * by Oliver Niese in his Ph.D. thesis. 040 * 041 * @author Malte Isberner <malte.isberner@gmail.com> 042 * 043 * @param <I> input symbol class 044 * @param <O> output symbol class 045 */ 046public class ClassicLStarMealy<I, O> extends 047 ExtensibleAutomatonLStar<MealyMachine<?, I, ?, O>, I, O, Integer, CompactMealyTransition<O>, Void, O, CompactMealy<I,O>> { 048 049 050 public static <A extends MutableMealyMachine<?,I,?,O>,I,O> 051 ClassicLStarMealy<I,O> createForSymbolOracle(Alphabet<I> alphabet, 052 MembershipOracle<I,O> oracle, 053 List<Word<I>> initialSuffixes, 054 ObservationTableCEXHandler<I, O> cexHandler, 055 ClosingStrategy<? super I,? super O> closingStrategy) { 056 return new ClassicLStarMealy<>(alphabet, oracle, 057 initialSuffixes, 058 cexHandler, 059 closingStrategy); 060 } 061 062 public static <A extends MutableMealyMachine<?,I,?,O>,I,O> 063 ClassicLStarMealy<I,O> createForWordOracle(Alphabet<I> alphabet, 064 MembershipOracle<I,Word<O>> oracle, 065 List<Word<I>> initialSuffixes, 066 ObservationTableCEXHandler<? super I, ? super O> cexHandler, 067 ClosingStrategy<? super I,? super O> closingStrategy) { 068 return new ClassicLStarMealy<>(alphabet, MealyUtil.wrapWordOracle(oracle), 069 initialSuffixes, 070 cexHandler, 071 closingStrategy); 072 } 073 074 075 /** 076 * Constructor. 077 * @param alphabet the learning alphabet 078 * @param oracle the (Mealy) oracle 079 */ 080 public ClassicLStarMealy(Alphabet<I> alphabet, 081 MembershipOracle<I, O> oracle, 082 List<Word<I>> initialSuffixes, 083 ObservationTableCEXHandler<? super I, ? super O> cexHandler, 084 ClosingStrategy<? super I, ? super O> closingStrategy) { 085 super(alphabet, oracle, new CompactMealy<I,O>(alphabet), 086 LStarMealyUtil.ensureSuffixCompliancy(initialSuffixes, alphabet, true), 087 cexHandler, 088 closingStrategy); 089 } 090 091 092 093 /* 094 * (non-Javadoc) 095 * @see de.learnlib.lstar.AbstractAutomatonLStar#stateProperty(de.learnlib.lstar.Row) 096 */ 097 @Override 098 protected Void stateProperty(Row<I> stateRow) { 099 return null; 100 } 101 102 /* 103 * (non-Javadoc) 104 * @see de.learnlib.lstar.AbstractAutomatonLStar#transitionProperty(de.learnlib.lstar.Row, int) 105 */ 106 @Override 107 protected O transitionProperty(Row<I> stateRow, int inputIdx) { 108 return table.cellContents(stateRow, inputIdx); 109 } 110 111 /* 112 * (non-Javadoc) 113 * @see de.learnlib.lstar.AbstractLStar#initialSuffixes() 114 */ 115 @Override 116 protected List<Word<I>> initialSuffixes() { 117 List<Word<I>> suffixes = new ArrayList<Word<I>>(alphabet.size()); 118 for(int i = 0; i < alphabet.size(); i++) { 119 I sym = alphabet.getSymbol(i); 120 suffixes.add(Word.fromLetter(sym)); 121 } 122 return suffixes; 123 } 124 125 /* 126 * (non-Javadoc) 127 * @see de.learnlib.lstar.AbstractAutomatonLStar#exposeInternalHypothesis() 128 */ 129 @Override 130 protected MealyMachine<?, I, ?, O> exposeInternalHypothesis() { 131 return internalHyp; 132 } 133 134 @Override 135 protected SuffixOutput<I, O> hypothesisOutput() { 136 return new SuffixOutput<I,O>() { 137 @Override 138 public O computeOutput(Iterable<I> input) { 139 return computeSuffixOutput(Collections.<I>emptyList(), input); 140 } 141 @Override 142 public O computeSuffixOutput(Iterable<I> prefix, Iterable<I> suffix) { 143 Word<O> wordOut = internalHyp.computeSuffixOutput(prefix, suffix); 144 if(wordOut.isEmpty()) 145 return null; 146 return wordOut.lastSymbol(); 147 } 148 149 }; 150 } 151 152}