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.mealy; 018 019import java.util.Objects; 020 021import net.automatalib.automata.transout.MealyMachine; 022import net.automatalib.words.Word; 023import de.learnlib.api.LearningAlgorithm; 024import de.learnlib.api.MembershipOracle; 025import de.learnlib.oracles.DefaultQuery; 026 027 028/** 029 * Utility class helping to unify various approaches to actively learning 030 * Mealy machines. 031 * 032 * @author Malte Isberner <malte.isberner@gmail.com> 033 * 034 */ 035public abstract class MealyUtil { 036 037 public static final int NO_MISMATCH = -1; 038 039 public static <O> int findMismatch(Word<O> out1, Word<O> out2) { 040 int len = out1.length(); 041 assert len == out2.length(); 042 043 for(int i = 0; i < len; i++) { 044 O sym1 = out1.getSymbol(i); 045 O sym2 = out2.getSymbol(i); 046 047 if(!Objects.equals(sym1, sym2)) 048 return i; 049 } 050 051 return NO_MISMATCH; 052 } 053 054 055 public static <I,O> DefaultQuery<I,Word<O>> shortenCounterExample( 056 MealyMachine<?,I,?,O> hypothesis, 057 DefaultQuery<I,Word<O>> ceQuery) { 058 Word<I> cePrefix = ceQuery.getPrefix(), ceSuffix = ceQuery.getSuffix(); 059 Word<O> hypOut = hypothesis.computeSuffixOutput(cePrefix, ceSuffix); 060 Word<O> ceOut = ceQuery.getOutput(); 061 assert ceOut.length() == hypOut.length(); 062 063 int mismatchIdx = findMismatch(hypOut, ceOut); 064 if(mismatchIdx == NO_MISMATCH) 065 return null; 066 067 return new DefaultQuery<>(cePrefix, 068 ceSuffix.prefix(mismatchIdx + 1), 069 ceOut.prefix(mismatchIdx + 1)); 070 } 071 072 public static <I,O> DefaultQuery<I,O> reduceCounterExample( 073 MealyMachine<?,I,?,O> hypothesis, 074 DefaultQuery<I,Word<O>> ceQuery) { 075 Word<I> cePrefix = ceQuery.getPrefix(), ceSuffix = ceQuery.getSuffix(); 076 Word<O> hypOut = hypothesis.computeSuffixOutput(cePrefix, ceSuffix); 077 Word<O> ceOut = ceQuery.getOutput(); 078 assert ceOut.length() == hypOut.length(); 079 080 int mismatchIdx = findMismatch(hypOut, ceOut); 081 if(mismatchIdx == NO_MISMATCH) 082 return null; 083 084 return new DefaultQuery<>(cePrefix, 085 ceSuffix.prefix(mismatchIdx + 1), 086 ceOut.getSymbol(mismatchIdx)); 087 } 088 089 090 public static <M extends MealyMachine<?,I,?,O>,I,O> 091 LearningAlgorithm<M,I,Word<O>> wrapSymbolLearner(LearningAlgorithm<M,I,O> learner) { 092 return new MealyLearnerWrapper<>(learner); 093 } 094 095 public static <I,O> MembershipOracle<I, O> wrapWordOracle(MembershipOracle<I,Word<O>> oracle) { 096 return new SymbolOracleWrapper<>(oracle); 097 } 098 099 // Prevent inheritance 100 private MealyUtil() {} 101 102}