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}