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; 018 019import java.util.ArrayList; 020 021import net.automatalib.automata.MutableDeterministic; 022import net.automatalib.commons.util.collections.CollectionsUtil; 023import net.automatalib.words.Alphabet; 024import de.learnlib.algorithms.lstargeneric.table.Row; 025import de.learnlib.api.MembershipOracle; 026 027 028/** 029 * Abstract base class for algorithms that produce (subclasses of) {@link MutableDeterministic} 030 * automata. 031 * 032 * This class provides the L*-style hypothesis construction. Implementing classes solely have 033 * to specify how state and transition properties should be derived. 034 * 035 * @author Malte Isberner <malte.isberner@gmail.com> 036 * 037 * @param <A> automaton class, must be a subclass of {@link MutableDeterministic} 038 * @param <I> input symbol class 039 * @param <O> output class 040 * @param <SP> state property class 041 * @param <TP> transition property class 042 */ 043public abstract class AbstractAutomatonLStar<A,I,O,S,T,SP,TP,AI extends MutableDeterministic<S,I,T,SP,TP>> extends 044 AbstractLStar<A, I, O> { 045 046 private static final class StateInfo<S,I> { 047 private final Row<I> row; 048 private final S state; 049 050 public StateInfo(Row<I> row, S state) { 051 this.row = row; 052 this.state = state; 053 } 054 055 public Row<I> getRow() { 056 return row; 057 } 058 059 public S getState() { 060 return state; 061 } 062 063 // IDENTITY SEMANTICS! 064 } 065 066 protected final AI internalHyp; 067 protected final ArrayList<StateInfo<S,I>> stateInfos 068 = new ArrayList<>(); 069 070 /** 071 * Constructor. 072 * @param alphabet the learning alphabet 073 * @param oracle the learning oracle 074 */ 075 public AbstractAutomatonLStar(Alphabet<I> alphabet, 076 MembershipOracle<I, O> oracle, 077 AI internalHyp) { 078 super(alphabet, oracle); 079 this.internalHyp = internalHyp; 080 internalHyp.clear(); 081 } 082 083 /** 084 * Derives a state property from the corresponding row. 085 * @param stateRow the row for which the state is created 086 * @return the state property of the corresponding state 087 */ 088 protected abstract SP stateProperty(Row<I> stateRow); 089 090 /** 091 * Derives a transition property from the corresponding transition. 092 * N.B.: Not the transition row is passed to this method, but the 093 * row for the outgoing state. The transition row can be retrieved 094 * by <code>stateRow.getSuccessor(inputIdx)</code>. 095 * @param stateRow the row for the source state 096 * @param inputIdx the index of the input symbol to consider 097 * @return the transition property of the corresponding transition 098 */ 099 protected abstract TP transitionProperty(Row<I> stateRow, int inputIdx); 100 101 102 protected abstract A exposeInternalHypothesis(); 103 104 /** 105 * Performs the L*-style hypothesis construction. 106 * For creating states and transitions, the {@link #stateProperty(Row)} and 107 * {@link #transitionProperty(Row, int)} methods are used to derive the 108 * respective properties. 109 * @param model the model to output 110 */ 111 protected void updateInternalHypothesis() { 112 if(!table.isInitialized()) 113 throw new IllegalStateException("Cannot update internal hypothesis: not initialized"); 114 115 int oldStates = internalHyp.size(); 116 int numDistinct = table.numDistinctRows(); 117 118 119 int newStates = numDistinct - oldStates; 120 121 if(newStates <= 0) 122 return; 123 124 stateInfos.addAll(CollectionsUtil.<StateInfo<S,I>>nullList(newStates)); 125 126 127 // TODO: Is there a quicker way than iterating over *all* rows? 128 // FIRST PASS: Create new hypothesis states 129 for(Row<I> sp : table.getShortPrefixRows()) { 130 int id = sp.getRowContentId(); 131 StateInfo<S,I> info = stateInfos.get(id); 132 if(info != null) { 133 // State from previous hypothesis, property might have changed 134 if(info.getRow() == sp) 135 internalHyp.setStateProperty(info.getState(), stateProperty(sp)); 136 continue; 137 } 138 139 S state = createState((id == 0), sp); 140 141 stateInfos.set(id, new StateInfo<>(sp, state)); 142 } 143 144 // SECOND PASS: Create hypothesis transitions 145 for(StateInfo<S,I> info : stateInfos) { 146 Row<I> sp = info.getRow(); 147 int rowId = sp.getRowContentId(); 148 S state = info.getState(); 149 150 for(int i = 0; i < alphabet.size(); i++) { 151 I input = alphabet.getSymbol(i); 152 153 Row<I> succ = sp.getSuccessor(i); 154 int succId = succ.getRowContentId(); 155 156 if(rowId < oldStates && succId < oldStates) 157 continue; 158 159 S succState = stateInfos.get(succId).getState(); 160 161 setTransition(state, input, succState, sp, i, succ); 162 } 163 } 164 } 165 166 protected S createState(boolean initial, Row<I> row) { 167 SP prop = stateProperty(row); 168 if(initial) 169 return internalHyp.addInitialState(prop); 170 return internalHyp.addState(prop); 171 } 172 173 protected void setTransition(S from, I input, S to, Row<I> fromRow, int inputIdx, Row<I> toRow) { 174 TP prop = transitionProperty(fromRow, inputIdx); 175 internalHyp.setTransition(from, input, to, prop); 176 } 177 178 @Override 179 public A getHypothesisModel() { 180 updateInternalHypothesis(); 181 return exposeInternalHypothesis(); 182 } 183 184}