001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib 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 * AutomataLib 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 AutomataLib; if not, see 015 * <http://www.gnu.de/documents/lgpl.en.html>. 016 */ 017 018package de.learnlib.examples.dfa; 019 020import net.automatalib.automata.fsa.DFA; 021import net.automatalib.automata.fsa.MutableDFA; 022import net.automatalib.automata.fsa.impl.compact.CompactDFA; 023import net.automatalib.words.Alphabet; 024import net.automatalib.words.impl.Alphabets; 025 026/** 027 * This class provides the example used in the paper ''Learning Regular Sets 028 * from Queries and Counterexamples'' by Dana Angluin that consists of an 029 * automaton that accepts ''all strings over {0,1} with an even number of 0's 030 * and an even number of 1's.'' 031 * 032 * @author Oliver Bauer <oliver.bauer@tu-dortmund.de> 033 */ 034public class ExampleAngluin { 035 036 private static final class InstanceHolder { 037 public static final DFA<?,Integer> INSTANCE; 038 039 static { 040 INSTANCE = constructMachine(); 041 } 042 } 043 044 private static final Alphabet<Integer> ALPHABET = Alphabets.integers(0, 1); 045 046 047 public static Alphabet<Integer> getInputAlphabet() { 048 return ALPHABET; 049 } 050 051 public static DFA<?,Integer> getInstance() { 052 return InstanceHolder.INSTANCE; 053 } 054 055 056 public static <A extends MutableDFA<S, ? super Integer>,S> 057 A constructMachine(A machine) { 058 S q0 = machine.addInitialState(true); 059 S q1 = machine.addState(false), q2 = machine.addState(false), q3 = machine.addState(false); 060 061 machine.addTransition(q0, 0, q1); 062 machine.addTransition(q0, 1, q2); 063 064 machine.addTransition(q1, 0, q0); 065 machine.addTransition(q1, 1, q3); 066 067 machine.addTransition(q2, 0, q3); 068 machine.addTransition(q2, 1, q0); 069 070 machine.addTransition(q3, 0, q2); 071 machine.addTransition(q3, 1, q1); 072 073 return machine; 074 } 075 076 public static CompactDFA<Integer> constructMachine() { 077 return constructMachine(new CompactDFA<>(ALPHABET)); 078 } 079 080 081 082 083 084}