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}