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}