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.eqtests.basic; 018 019import java.util.Collection; 020import java.util.Collections; 021import java.util.List; 022import java.util.Objects; 023 024import net.automatalib.automata.concepts.DetOutputAutomaton; 025import net.automatalib.commons.util.collections.CollectionsUtil; 026import net.automatalib.words.Word; 027import de.learnlib.api.EquivalenceOracle; 028import de.learnlib.api.MembershipOracle; 029import de.learnlib.oracles.DefaultQuery; 030 031/** 032 * Implements an equivalence check by complete exploration up to a given depth, i.e., 033 * by testing all possible sequences of a certain length within a specified range. 034 * 035 * @author Malte Isberner <malte.isberner@gmail.com> 036 * 037 * @param <I> input symbol class 038 * @param <O> output class 039 */ 040public class CompleteExplorationEQOracle<I, O> implements 041 EquivalenceOracle<DetOutputAutomaton<?, I, ?, O>, I, O> { 042 043 private int minDepth; 044 private int maxDepth; 045 private final MembershipOracle<I, O> sulOracle; 046 047 /** 048 * Constructor. 049 * @param sulOracle interface to the system under learning 050 * @param maxDepth maximum exploration depth 051 */ 052 public CompleteExplorationEQOracle(MembershipOracle<I, O> sulOracle, int maxDepth) { 053 this(sulOracle, 1, maxDepth); 054 } 055 056 /** 057 * Constructor. 058 * @param sulOracle interface to the system under learning 059 * @param minDepth minimum exploration depth 060 * @param maxDepth maximum exploration depth 061 */ 062 public CompleteExplorationEQOracle(MembershipOracle<I, O> sulOracle, int minDepth, int maxDepth) { 063 if(maxDepth < minDepth) 064 maxDepth = minDepth; 065 066 this.minDepth = minDepth; 067 this.maxDepth = maxDepth; 068 069 this.sulOracle = sulOracle; 070 } 071 072 /* 073 * (non-Javadoc) 074 * @see de.learnlib.api.EquivalenceOracle#findCounterExample(java.lang.Object, java.util.Collection) 075 */ 076 @Override 077 public DefaultQuery<I, O> findCounterExample(DetOutputAutomaton<?,I,?,O> hypothesis, 078 Collection<? extends I> alphabet) { 079 for(List<? extends I> symList : CollectionsUtil.allTuples(alphabet, minDepth, maxDepth)) { 080 Word<I> queryWord = Word.fromList(symList); 081 082 DefaultQuery<I,O> query = new DefaultQuery<>(queryWord); 083 O hypOutput = hypothesis.computeOutput(queryWord); 084 sulOracle.processQueries(Collections.singleton(query)); 085 086 if(!Objects.equals(hypOutput, query.getOutput())) 087 return query; 088 } 089 090 return null; 091 } 092 093}