de.learnlib.algorithms.lstargeneric.dfa

Class ExtensibleLStarDFA<I>

java.lang.Object

de.learnlib.algorithms.lstargeneric.AbstractLStar<A,I,O>

de.learnlib.algorithms.lstargeneric.AbstractAutomatonLStar<A,I,O,S,T,SP,TP,AI>

de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>

de.learnlib.algorithms.lstargeneric.dfa.ExtensibleLStarDFA<I>

Type Parameters:

I - input symbol class.

All Implemented Interfaces:

LearningAlgorithm<DFA<?,I>,I,Boolean>, LearningAlgorithm.DFALearner<I>

public class ExtensibleLStarDFA<I>
extends ExtensibleAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>
implements LearningAlgorithm.DFALearner<I>

An implementation of Angluin's L* algorithm for learning DFAs, as described in the paper "Learning Regular Sets from Queries and Counterexamples".

Author:

Malte Isberner

Nested Class Summary

Nested classes/interfaces inherited from interface de.learnlib.api.LearningAlgorithm

LearningAlgorithm.DFALearner<I>, LearningAlgorithm.MealyLearner<I,O>

Field Summary

Fields inherited from class de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar

cexHandler, closingStrategy, initialSuffixes

Fields inherited from class de.learnlib.algorithms.lstargeneric.AbstractAutomatonLStar

internalHyp, stateInfos

Fields inherited from class de.learnlib.algorithms.lstargeneric.AbstractLStar

alphabet, oracle, table

Constructor Summary

Constructors

Constructor and Description
ExtensibleLStarDFA(Alphabet<I> alphabet, MembershipOracle<I,Boolean> oracle, List<Word<I>> initialSuffixes, ObservationTableCEXHandler<? super I,? super Boolean> cexHandler, ClosingStrategy<? super I,? super Boolean> closingStrategy) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected DFA<?,I>	exposeInternalHypothesis()
protected SuffixOutput<I,Boolean>	hypothesisOutput()
protected List<Word<I>>	initialSuffixes() Returns the list of initial suffixes which are used to initialize the table.
protected Boolean	stateProperty(Row<I> stateRow) Derives a state property from the corresponding row.
protected Void	transitionProperty(Row<I> stateRow, int inputIdx) Derives a transition property from the corresponding transition.

Methods inherited from class de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar

doRefineHypothesis, selectClosingRows

Methods inherited from class de.learnlib.algorithms.lstargeneric.AbstractAutomatonLStar

createState, getHypothesisModel, setTransition, updateInternalHypothesis

Methods inherited from class de.learnlib.algorithms.lstargeneric.AbstractLStar

analyzeInconsistency, completeConsistentTable, incorporateCounterExample, refineHypothesis, startLearning

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.learnlib.api.LearningAlgorithm

getHypothesisModel, refineHypothesis, startLearning

Constructor Detail

ExtensibleLStarDFA

public ExtensibleLStarDFA(Alphabet<I> alphabet,
                  MembershipOracle<I,Boolean> oracle,
                  List<Word<I>> initialSuffixes,
                  ObservationTableCEXHandler<? super I,? super Boolean> cexHandler,
                  ClosingStrategy<? super I,? super Boolean> closingStrategy)

Constructor.

Parameters:

alphabet - the learning alphabet.

oracle - the DFA oracle.

Method Detail

initialSuffixes

protected List<Word<I>> initialSuffixes()

Description copied from class: AbstractLStar

Returns the list of initial suffixes which are used to initialize the table.

Overrides:

initialSuffixes in class ExtensibleAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>

Returns:

the list of initial suffixes.

stateProperty

protected Boolean stateProperty(Row<I> stateRow)

Description copied from class: AbstractAutomatonLStar

Derives a state property from the corresponding row.

Specified by:

stateProperty in class AbstractAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>

Parameters:

stateRow - the row for which the state is created

Returns:

the state property of the corresponding state

transitionProperty

protected Void transitionProperty(Row<I> stateRow,
                      int inputIdx)

Description copied from class: AbstractAutomatonLStar

Derives a transition property from the corresponding transition. N.B.: Not the transition row is passed to this method, but the row for the outgoing state. The transition row can be retrieved by stateRow.getSuccessor(inputIdx).

Specified by:

transitionProperty in class AbstractAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>

Parameters:

stateRow - the row for the source state

inputIdx - the index of the input symbol to consider

Returns:

the transition property of the corresponding transition

exposeInternalHypothesis

protected DFA<?,I> exposeInternalHypothesis()

Specified by:

exposeInternalHypothesis in class AbstractAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>

hypothesisOutput

protected SuffixOutput<I,Boolean> hypothesisOutput()

Specified by:

hypothesisOutput in class ExtensibleAutomatonLStar<DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,CompactDFA<I>>