Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
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