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.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.List;
023import java.util.Random;
024
025import net.automatalib.automata.concepts.OutputAutomaton;
026import net.automatalib.words.WordBuilder;
027import de.learnlib.api.EquivalenceOracle;
028import de.learnlib.api.MembershipOracle;
029import de.learnlib.oracles.DefaultQuery;
030
031/**
032 *
033 * @author Maik Merten <maikmerten@googlemail.com>
034 */
035public class RandomWordsEQOracle<I, O, A extends OutputAutomaton<?, I, ?, O>> implements EquivalenceOracle<A, I, O> {
036
037        private MembershipOracle<I, O> oracle;
038        private int maxTests, minLength, maxLength;
039        private final Random random;
040
041        public RandomWordsEQOracle(MembershipOracle<I, O> mqOracle, int minLength, int maxLength, int maxTests, Random random) {
042                this.oracle = mqOracle;
043                this.maxTests = maxTests;
044                this.minLength = minLength;
045                this.maxLength = maxLength;
046                this.random = random;
047        }
048
049        @Override
050        public DefaultQuery<I, O> findCounterExample(A hypothesis, Collection<? extends I> alpha) {
051
052                List<? extends I> symbolList;
053                if (alpha instanceof List) {
054                        symbolList = (List<? extends I>) alpha;
055                } else {
056                        symbolList = new ArrayList<>(alpha);
057                }
058                
059                int numSyms = symbolList.size();
060
061                for (int i = 0; i < maxTests; ++i) {
062                        int length = minLength + random.nextInt((maxLength - minLength) + 1);
063
064                        WordBuilder<I> testtrace = new WordBuilder<>(length);
065                        for (int j = 0; j < length; ++j) {
066                                int symidx = random.nextInt(numSyms);
067                                I sym = symbolList.get(symidx);
068                                testtrace.append(sym);
069                        }
070
071                        DefaultQuery<I, O> query = new DefaultQuery<>(testtrace.toWord());
072
073                        // query oracle
074                        oracle.processQueries(Collections.singletonList(query));
075                        O oracleoutput = query.getOutput();
076
077                        // trace hypothesis
078                        O hypOutput = hypothesis.computeOutput(testtrace.toWord());
079
080                        // compare output of hypothesis and oracle
081                        if (!oracleoutput.equals(hypOutput)) {
082                                return query;
083                        }
084                }
085
086                // no counterexample found
087                return null;
088        }
089}