Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
AutomataUnionEpsilonTransition.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
29
30namespace automaton {
31
32namespace transform {
33
40public:
49 template < class SymbolType, class StateType >
51
55 template < class SymbolType, class StateType >
57
61 template < class SymbolType, class StateType >
63
64};
65
66template < class SymbolType, class StateType >
68 unsigned firstDefault = 1;
69 unsigned secondDefault = 2;
70
71 ext::pair < StateType, unsigned > q0 = ext::make_pair ( label::InitialStateLabel::instance < StateType > ( ), 0 );
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 res.addTransition ( q0, ext::make_pair ( first.getInitialState ( ), firstDefault ) );
90 res.addTransition ( q0, ext::make_pair ( second.getInitialState ( ), secondDefault ) );
91
92 for(const auto& t : first.getTransitions())
93 res.addTransition ( ext::make_pair ( t.first.first, firstDefault ), t.first.second, ext::make_pair ( t.second, firstDefault ) );
94
95 for(const auto& t : second.getTransitions())
96 res.addTransition ( ext::make_pair ( t.first.first, secondDefault ), t.first.second, ext::make_pair ( t.second, secondDefault ) );
97
98 return res;
99}
100
101template < class SymbolType, class StateType >
103 unsigned firstDefault = 1;
104 unsigned secondDefault = 2;
105
106 ext::pair < StateType, unsigned > q0 = ext::make_pair ( label::InitialStateLabel::instance < StateType > ( ), 0 );
108
109 for(const auto& a : first.getInputAlphabet())
110 res.addInputSymbol(a);
111 for(const auto& a : second.getInputAlphabet())
112 res.addInputSymbol(a);
113
114 for ( const auto & q : first.getStates ( ) )
115 res.addState ( ext::make_pair ( q, firstDefault ) );
116 for ( const auto & q : second.getStates ( ) )
117 res.addState ( ext::make_pair ( q, secondDefault ) );
118
119 for(const auto& q : first.getFinalStates())
120 res.addFinalState ( ext::make_pair ( q, firstDefault ) );
121 for(const auto& q : second.getFinalStates())
122 res.addFinalState ( ext::make_pair ( q, secondDefault ) );
123
124 res.addTransition ( q0, ext::make_pair ( first.getInitialState ( ), firstDefault ) );
125 res.addTransition ( q0, ext::make_pair ( second.getInitialState ( ), secondDefault ) );
126
127 for(const auto& t : first.getTransitions())
128 res.addTransition ( ext::make_pair ( t.first.first, firstDefault ), t.first.second, ext::make_pair ( t.second, firstDefault ) );
129
130 for(const auto& t : second.getTransitions())
131 res.addTransition ( ext::make_pair ( t.first.first, secondDefault ), t.first.second, ext::make_pair ( t.second, secondDefault ) );
132
133 return res;
134}
135
136template < class SymbolType, class StateType >
138 unsigned firstDefault = 1;
139 unsigned secondDefault = 2;
140
141 ext::pair < StateType, unsigned > q0 = ext::make_pair ( label::InitialStateLabel::instance < StateType > ( ), 0 );
143
144 for(const auto& a : first.getInputAlphabet())
145 res.addInputSymbol(a);
146 for(const auto& a : second.getInputAlphabet())
147 res.addInputSymbol(a);
148
149 for ( const auto & q : first.getStates ( ) )
150 res.addState ( ext::make_pair ( q, firstDefault ) );
151 for ( const auto & q : second.getStates ( ) )
152 res.addState ( ext::make_pair ( q, secondDefault ) );
153
154 for(const auto& q : first.getFinalStates())
155 res.addFinalState ( ext::make_pair ( q, firstDefault ) );
156 for(const auto& q : second.getFinalStates())
157 res.addFinalState ( ext::make_pair ( q, secondDefault ) );
158
159 res.addTransition ( q0, ext::make_pair ( first.getInitialState ( ), firstDefault ) );
160 res.addTransition ( q0, ext::make_pair ( second.getInitialState ( ), secondDefault ) );
161
162 for(const auto& t : first.getTransitions())
163 res.addTransition ( ext::make_pair ( t.first.first, firstDefault ), t.first.second, ext::make_pair ( t.second, firstDefault ) );
164
165 for(const auto& t : second.getTransitions())
166 res.addTransition ( ext::make_pair ( t.first.first, secondDefault ), t.first.second, ext::make_pair ( t.second, secondDefault ) );
167
168 return res;
169}
170
171} /* namespace transform */
172
173} /* namespace automaton */
174
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
const ext::set< StateType > & getFinalStates() const &
Definition: DFA.h:183
const ext::map< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: DFA.h:473
const StateType & getInitialState() const &
Definition: DFA.h:105
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: DFA.h:232
const ext::set< StateType > & getStates() const &
Definition: DFA.h:134
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
const ext::set< StateType > & getStates() const &
Definition: EpsilonNFA.h:158
const ext::set< StateType > & getFinalStates() const &
Definition: EpsilonNFA.h:207
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: EpsilonNFA.h:256
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > & getTransitions() const &
Definition: EpsilonNFA.h:666
const StateType & getInitialState() const &
Definition: EpsilonNFA.h:129
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
const ext::set< StateType > & getStates() const &
Definition: NFA.h:136
const StateType & getInitialState() const &
Definition: NFA.h:107
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: NFA.h:234
const ext::multimap< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: NFA.h:484
const ext::set< StateType > & getFinalStates() const &
Definition: NFA.h:185
Definition: AutomataUnionEpsilonTransition.h:39
static automaton::EpsilonNFA< SymbolType, ext::pair< StateType, unsigned > > unification(const automaton::EpsilonNFA< SymbolType, StateType > &first, const automaton::EpsilonNFA< SymbolType, StateType > &second)
Definition: AutomataUnionEpsilonTransition.h:67
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
q
Definition: SingleInitialStateEpsilonTransition.h:85
StateType q0
Definition: SingleInitialState.h:96
return res
Definition: AutomataConcatenation.h:102
t first second
Definition: AutomataConcatenation.h:78
Definition: ToGrammar.h:31
ContainerType< ResType > transform(const ContainerType< InType, Ts ... > &in, Callback transform)
In container tranformation of all elements according to the tranform.
Definition: algorithm.hpp:150
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79