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.dfa;
018
019import java.util.Collections;
020import java.util.List;
021
022import net.automatalib.automata.concepts.SuffixOutput;
023import net.automatalib.automata.fsa.DFA;
024import net.automatalib.automata.fsa.impl.compact.CompactDFA;
025import net.automatalib.words.Alphabet;
026import net.automatalib.words.Word;
027import de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar;
028import de.learnlib.algorithms.lstargeneric.ce.ObservationTableCEXHandler;
029import de.learnlib.algorithms.lstargeneric.closing.ClosingStrategy;
030import de.learnlib.algorithms.lstargeneric.table.Row;
031import de.learnlib.api.LearningAlgorithm.DFALearner;
032import de.learnlib.api.MembershipOracle;
033
034
035/**
036 * An implementation of Angluin's L* algorithm for learning DFAs, as described in the paper
037 * "Learning Regular Sets from Queries and Counterexamples".
038 * 
039 * @author Malte Isberner <malte.isberner@gmail.com>
040 *
041 * @param <I> input symbol class.
042 */
043public class ExtensibleLStarDFA<I>
044        extends ExtensibleAutomatonLStar<DFA<?,I>, I, Boolean, Integer, Integer, Boolean, Void, CompactDFA<I>> implements DFALearner<I> {
045
046        
047        /**
048         * Constructor.
049         * @param alphabet the learning alphabet.
050         * @param oracle the DFA oracle.
051         */
052        public ExtensibleLStarDFA(Alphabet<I> alphabet, MembershipOracle<I,Boolean> oracle,
053                        List<Word<I>> initialSuffixes,
054                        ObservationTableCEXHandler<? super I, ? super Boolean> cexHandler,
055                        ClosingStrategy<? super I, ? super Boolean> closingStrategy) {
056                super(alphabet, oracle, new CompactDFA<I>(alphabet),
057                                LStarDFAUtil.ensureSuffixCompliancy(initialSuffixes),
058                                cexHandler, closingStrategy);
059        }
060
061        
062        /*
063         * (non-Javadoc)
064         * @see de.learnlib.lstar.AbstractLStar#initialSuffixes()
065         */
066        @Override
067        protected List<Word<I>> initialSuffixes() {
068                return Collections.singletonList(Word.<I>epsilon());
069        }
070
071
072        /*
073         * (non-Javadoc)
074         * @see de.learnlib.lstar.AbstractAutomatonLStar#stateProperty(de.learnlib.lstar.Row)
075         */
076        @Override
077        protected Boolean stateProperty(Row<I> stateRow) {
078                return table.cellContents(stateRow, 0);
079        }
080
081        /*
082         * (non-Javadoc)
083         * @see de.learnlib.lstar.AbstractAutomatonLStar#transitionProperty(de.learnlib.lstar.Row, int)
084         */
085        @Override
086        protected Void transitionProperty(Row<I> stateRow, int inputIdx) {
087                return null;
088        }
089
090
091        /*
092         * (non-Javadoc)
093         * @see de.learnlib.algorithms.lstargeneric.AbstractAutomatonLStar#exposeInternalHypothesis()
094         */
095        @Override
096        protected DFA<?, I> exposeInternalHypothesis() {
097                return internalHyp;
098        }
099
100        /*
101         * (non-Javadoc)
102         * @see de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar#hypothesisOutput()
103         */
104        @Override
105        protected SuffixOutput<I, Boolean> hypothesisOutput() {
106                return internalHyp;
107        }
108
109
110}