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}