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 */ 017package net.automatalib.util.automata.fsa; 018 019import java.util.Collection; 020 021import net.automatalib.automata.fsa.DFA; 022import net.automatalib.automata.fsa.MutableDFA; 023import net.automatalib.automata.fsa.impl.FastDFA; 024import net.automatalib.commons.util.mappings.Mapping; 025import net.automatalib.commons.util.mappings.Mappings; 026import net.automatalib.ts.acceptors.DeterministicAcceptorTS; 027import net.automatalib.util.automata.copy.AutomatonCopy; 028import net.automatalib.util.ts.acceptors.AcceptanceCombiner; 029import net.automatalib.util.ts.acceptors.Acceptors; 030import net.automatalib.words.Alphabet; 031 032 033public abstract class DFAs { 034 035 private static final Mapping<Boolean,Boolean> NEGATE 036 = new Mapping<Boolean,Boolean>() { 037 @Override 038 public Boolean get(Boolean elem) { 039 return !elem; 040 } 041 }; 042 043 public static <I,S,A extends MutableDFA<S,I>> 044 A combine(DFA<?,I> dfa1, DFA<?,I> dfa2, 045 Collection<? extends I> inputs, 046 A out, 047 AcceptanceCombiner combiner) { 048 DeterministicAcceptorTS<?, I> acc 049 = Acceptors.combine(dfa1, dfa2, combiner); 050 051 AutomatonCopy.copyUniversalDfs(acc, inputs, out, Mappings.<I>identity()); 052 return out; 053 } 054 055 056 057 public static <I> FastDFA<I> combine(DFA<?,I> dfa1, DFA<?,I> dfa2, 058 Alphabet<I> inputAlphabet, 059 AcceptanceCombiner combiner) { 060 return combine(dfa1, dfa2, inputAlphabet, new FastDFA<I>(inputAlphabet), combiner); 061 } 062 063 public static <I,S,A extends MutableDFA<S,I>> 064 A and(DFA<?,I> dfa1, DFA<?,I> dfa2, 065 Collection<? extends I> inputs, A out) { 066 return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.AND); 067 } 068 069 public static <I> 070 FastDFA<I> and(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet) { 071 return and(dfa1, dfa2, inputAlphabet, new FastDFA<I>(inputAlphabet)); 072 } 073 074 public static <I,S,A extends MutableDFA<S,I>> 075 A or(DFA<?,I> dfa1, DFA<?,I> dfa2, 076 Collection<? extends I> inputs, A out) { 077 return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.OR); 078 } 079 080 public static <I> 081 FastDFA<I> or(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet) { 082 return or(dfa1, dfa2, inputAlphabet, new FastDFA<I>(inputAlphabet)); 083 } 084 085 public static <I,S,A extends MutableDFA<S,I>> 086 A xor(DFA<?,I> dfa1, DFA<?,I> dfa2, 087 Collection<? extends I> inputs, A out) { 088 return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.XOR); 089 } 090 091 public static <I> 092 FastDFA<I> xor(DFA<?,I> dfa1, DFA<?,I> dfa2, 093 Alphabet<I> inputAlphabet) { 094 return xor(dfa1, dfa2, inputAlphabet, new FastDFA<I>(inputAlphabet)); 095 } 096 097 public static <I,S,A extends MutableDFA<S,I>> 098 A equiv(DFA<?,I> dfa1, DFA<?,I> dfa2, 099 Collection<? extends I> inputs, A out) { 100 return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.EQUIV); 101 } 102 public static <I> FastDFA<I> equiv(DFA<?,I> dfa1, DFA<?,I> dfa2, 103 Alphabet<I> inputAlphabet) { 104 return equiv(dfa1, dfa2, inputAlphabet, new FastDFA<I>(inputAlphabet)); 105 } 106 107 public static <I,S,A extends MutableDFA<S,I>> 108 A impl(DFA<?,I> dfa1, DFA<?,I> dfa2, 109 Collection<? extends I> inputs, A out) { 110 return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.IMPL); 111 } 112 113 public static <I> FastDFA<I> impl(DFA<?,I> dfa1, DFA<?,I> dfa2, 114 Alphabet<I> inputAlphabet) { 115 return impl(dfa1, dfa2, inputAlphabet, new FastDFA<I>(inputAlphabet)); 116 } 117 118 public static <I,S,A extends MutableDFA<S,I>> A complement(DFA<?,I> dfa, 119 Collection<? extends I> inputs, A out) { 120 AutomatonCopy.copyUniversalDfs(dfa, inputs, out, NEGATE, Mappings.<Void,Void>nullMapping()); 121 return out; 122 } 123 124 public static <I> FastDFA<I> complement(DFA<?,I> dfa, 125 Alphabet<I> inputAlphabet) { 126 return complement(dfa, inputAlphabet, new FastDFA<I>(inputAlphabet)); 127 } 128 129 130 131 132 133}