Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
AutomataUnion.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <automaton/FSM/EpsilonNFA.h>
27#include <label/InitialStateLabel.h>
28#include <common/createUnique.hpp>
29
30namespace automaton {
31
32namespace transform {
33
39class AutomataUnion {
40public:
49 template < class SymbolType, class StateType >
50 static automaton::EpsilonNFA < SymbolType, ext::pair < StateType, unsigned > > unification(const automaton::EpsilonNFA < SymbolType, StateType > & first, const automaton::EpsilonNFA < SymbolType, StateType > & second);
51
55 template < class SymbolType, class StateType >
56 static automaton::NFA < SymbolType, ext::pair < StateType, unsigned > > unification(const automaton::NFA < SymbolType, StateType > & first, const automaton::NFA < SymbolType, StateType > & second);
57
61 template < class SymbolType, class StateType >
62 static automaton::NFA < SymbolType, ext::pair < StateType, unsigned > > unification(const automaton::DFA < SymbolType, StateType > & first, const automaton::DFA < SymbolType, StateType > & second);
63
64};
65
66template < class SymbolType, class StateType >
67automaton::EpsilonNFA < SymbolType, ext::pair < StateType, unsigned > > AutomataUnion::unification(const automaton::EpsilonNFA < SymbolType, StateType > & first, const automaton::EpsilonNFA < SymbolType, StateType > & second) {
68 unsigned firstDefault = 1;
69 unsigned secondDefault = 2;
70
71 ext::pair < StateType, unsigned > q0 = ext::make_pair ( label::InitialStateLabel::instance < StateType > ( ), 0 );
72 automaton::EpsilonNFA < SymbolType, ext::pair < StateType, unsigned > > res ( q0 );
73
74 for(const auto& a : first.getInputAlphabet())
75 res.addInputSymbol(a);
76 for(const auto& a : second.getInputAlphabet())
77 res.addInputSymbol(a);
78
79 for ( const auto & q : first.getStates ( ) )
80 res.addState ( ext::make_pair ( q, firstDefault ) );
81 for ( const auto & q : second.getStates ( ) )
82 res.addState ( ext::make_pair ( q, secondDefault ) );
83
84 for(const auto& q : first.getFinalStates())
85 res.addFinalState ( ext::make_pair ( q, firstDefault ) );
86 for(const auto& q : second.getFinalStates())
87 res.addFinalState ( ext::make_pair ( q, secondDefault ) );
88
89 if ( first.getFinalStates ( ).contains ( first.getInitialState ( ) ) || second.getFinalStates ( ).contains ( second.getInitialState ( ) ) )
90 res.addFinalState ( q0 );
91
92 for ( const auto & t : first.getTransitionsFromState ( first.getInitialState ( ) ) )
93 res.addTransition ( q0, t.first.second, ext::make_pair ( t.second, firstDefault ) );
94 for ( const auto & t : second.getTransitionsFromState ( second.getInitialState ( ) ) )
95 res.addTransition ( q0, t.first.second, ext::make_pair ( t.second, secondDefault ) );
96
97 for(const auto& t : first.getTransitions())
98 res.addTransition ( ext::make_pair ( t.first.first, firstDefault ), t.first.second, ext::make_pair ( t.second, firstDefault ) );
99
100 for(const auto& t : second.getTransitions())
101 res.addTransition ( ext::make_pair ( t.first.first, secondDefault ), t.first.second, ext::make_pair ( t.second, secondDefault ) );
102
103 return res;
104}
105
106template < class SymbolType, class StateType >
107automaton::NFA < SymbolType, ext::pair < StateType, unsigned > > AutomataUnion::unification(const automaton::NFA < SymbolType, StateType > & first, const automaton::NFA < SymbolType, StateType > & second) {
108 unsigned firstDefault = 1;
109 unsigned secondDefault = 2;
110
111 ext::pair < StateType, unsigned > q0 = ext::make_pair ( label::InitialStateLabel::instance < StateType > ( ), 0 );
112 automaton::NFA < SymbolType, ext::pair < StateType, unsigned > > res ( q0 );
113
114 for(const auto& a : first.getInputAlphabet())
115 res.addInputSymbol(a);
116 for(const auto& a : second.getInputAlphabet())
117 res.addInputSymbol(a);
118
119 for ( const auto & q : first.getStates ( ) )
120 res.addState ( ext::make_pair ( q, firstDefault ) );
121 for ( const auto & q : second.getStates ( ) )
122 res.addState ( ext::make_pair ( q, secondDefault ) );
123
124 for(const auto& q : first.getFinalStates())
125 res.addFinalState ( ext::make_pair ( q, firstDefault ) );
126 for(const auto& q : second.getFinalStates())
127 res.addFinalState ( ext::make_pair ( q, secondDefault ) );
128
129 if ( first.getFinalStates ( ).contains ( first.getInitialState ( ) ) || second.getFinalStates ( ).contains ( second.getInitialState ( ) ) )
130 res.addFinalState ( q0 );
131
132 for ( const auto & t : first.getTransitionsFromState ( first.getInitialState ( ) ) )
133 res.addTransition ( q0, t.first.second, ext::make_pair ( t.second, firstDefault ) );
134 for ( const auto & t : second.getTransitionsFromState ( second.getInitialState ( ) ) )
135 res.addTransition ( q0, t.first.second, ext::make_pair ( t.second, secondDefault ) );
136
137 for(const auto& t : first.getTransitions())
138 res.addTransition ( ext::make_pair ( t.first.first, firstDefault ), t.first.second, ext::make_pair ( t.second, firstDefault ) );
139
140 for(const auto& t : second.getTransitions())
141 res.addTransition ( ext::make_pair ( t.first.first, secondDefault ), t.first.second, ext::make_pair ( t.second, secondDefault ) );
142
143 return res;
144}
145
146template < class SymbolType, class StateType >
147automaton::NFA < SymbolType, ext::pair < StateType, unsigned > > AutomataUnion::unification(const automaton::DFA< SymbolType, StateType > & first, const automaton::DFA < SymbolType, StateType > & second) {
148 unsigned firstDefault = 1;
149 unsigned secondDefault = 2;
150
151 ext::pair < StateType, unsigned > q0 = ext::make_pair ( label::InitialStateLabel::instance < StateType > ( ), 0 );
152 automaton::NFA < SymbolType, ext::pair < StateType, unsigned > > res ( q0 );
153
154 for(const auto& a : first.getInputAlphabet())
155 res.addInputSymbol(a);
156 for(const auto& a : second.getInputAlphabet())
157 res.addInputSymbol(a);
158
159 for ( const auto & q : first.getStates ( ) )
160 res.addState ( ext::make_pair ( q, firstDefault ) );
161 for ( const auto & q : second.getStates ( ) )
162 res.addState ( ext::make_pair ( q, secondDefault ) );
163
164 for(const auto& q : first.getFinalStates())
165 res.addFinalState ( ext::make_pair ( q, firstDefault ) );
166 for(const auto& q : second.getFinalStates())
167 res.addFinalState ( ext::make_pair ( q, secondDefault ) );
168
169 if ( first.getFinalStates ( ).contains ( first.getInitialState ( ) ) || second.getFinalStates ( ).contains ( second.getInitialState ( ) ) )
170 res.addFinalState ( q0 );
171
172 for ( const auto & t : first.getTransitionsFromState ( first.getInitialState ( ) ) )
173 res.addTransition ( q0, t.first.second, ext::make_pair ( t.second, firstDefault ) );
174 for ( const auto & t : second.getTransitionsFromState ( second.getInitialState ( ) ) )
175 res.addTransition ( q0, t.first.second, ext::make_pair ( t.second, secondDefault ) );
176
177 for(const auto& t : first.getTransitions())
178 res.addTransition ( ext::make_pair ( t.first.first, firstDefault ), t.first.second, ext::make_pair ( t.second, firstDefault ) );
179
180 for(const auto& t : second.getTransitions())
181 res.addTransition ( ext::make_pair ( t.first.first, secondDefault ), t.first.second, ext::make_pair ( t.second, secondDefault ) );
182
183 return res;
184}
185
186} /* namespace transform */
187
188} /* namespace automaton */
189
automaton::DFA
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
automaton::DFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: DFA.h:183
automaton::DFA::getTransitions
const ext::map< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: DFA.h:473
automaton::DFA::getInitialState
const StateType & getInitialState() const &
Definition: DFA.h:105
automaton::DFA::getInputAlphabet
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: DFA.h:232
automaton::DFA::getStates
const ext::set< StateType > & getStates() const &
Definition: DFA.h:134
automaton::DFA::getTransitionsFromState
ext::iterator_range< typename ext::map< ext::pair< StateType, SymbolType >, StateType >::const_iterator > getTransitionsFromState(const StateType &from) const
Definition: DFA.h:483
automaton::EpsilonNFA
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
automaton::EpsilonNFA::getStates
const ext::set< StateType > & getStates() const &
Definition: EpsilonNFA.h:158
automaton::EpsilonNFA::getTransitionsFromState
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > getTransitionsFromState(const StateType &from) const
Definition: EpsilonNFA.h:698
automaton::EpsilonNFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: EpsilonNFA.h:207
automaton::EpsilonNFA::getInputAlphabet
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: EpsilonNFA.h:256
automaton::EpsilonNFA::getTransitions
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > & getTransitions() const &
Definition: EpsilonNFA.h:666
automaton::EpsilonNFA::getInitialState
const StateType & getInitialState() const &
Definition: EpsilonNFA.h:129
automaton::NFA
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
automaton::NFA::getStates
const ext::set< StateType > & getStates() const &
Definition: NFA.h:136
automaton::NFA::getInitialState
const StateType & getInitialState() const &
Definition: NFA.h:107
automaton::NFA::getInputAlphabet
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: NFA.h:234
automaton::NFA::getTransitions
const ext::multimap< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: NFA.h:484
automaton::NFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: NFA.h:185
automaton::NFA::getTransitionsFromState
auto getTransitionsFromState(const StateType &from) const
Definition: NFA.h:494
automaton::transform::AutomataUnion
Definition: AutomataUnion.h:39
automaton::transform::AutomataUnion::unification
static automaton::EpsilonNFA< SymbolType, ext::pair< StateType, unsigned > > unification(const automaton::EpsilonNFA< SymbolType, StateType > &first, const automaton::EpsilonNFA< SymbolType, StateType > &second)
Definition: AutomataUnion.h:67
ext::pair
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
automaton::simplify::q
q
Definition: SingleInitialStateEpsilonTransition.h:85
automaton::simplify::q0
StateType q0
Definition: SingleInitialState.h:96
automaton::transform::res
return res
Definition: AutomataConcatenation.h:102
automaton::transform::second
t first second
Definition: AutomataConcatenation.h:78
automaton
Definition: ToGrammar.h:31
ext::transform
ContainerType< ResType > transform(const ContainerType< InType, Ts ... > &in, Callback transform)
In container tranformation of all elements according to the tranform.
Definition: algorithm.hpp:150
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2