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
EpsilonClosure.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 <queue>
27
28#include <ext/algorithm>
29
30#include <alib/set>
31#include <alib/map>
32
37#include <automaton/FSM/NFA.h>
38#include <automaton/FSM/DFA.h>
40
42
43namespace automaton {
44
45namespace properties {
46
51public:
63 template < class SymbolType, class StateType >
65
77 template < class SymbolType, class StateType >
79
91 template < class T >
92 requires isDFA < T > || isNFA < T > || isMultiInitialStateNFA < T >
93 static ext::set < typename T::StateType > epsilonClosure ( const T & fsm, const typename T::StateType & q );
94
106 template < class SymbolType, class StateType >
108
120 template < class SymbolType, class StateType >
122};
123
124template < class SymbolType, class StateType >
126 if ( ! fsm.getStates ( ).contains ( q ) )
127 throw exception::CommonException ( "State is not in the automaton" );
128
130 std::queue < StateType > queue;
131 queue.push ( q );
132
133 while ( ! queue.empty( ) ) {
134 StateType p = std::move ( queue.front ( ) );
135 queue.pop ( );
136
137 auto tos = fsm.getTransitions ( ).equal_range ( ext::make_pair ( p, common::symbol_or_epsilon < SymbolType > ( ) ) );
138 for ( const auto & transition : tos )
139 if ( closure.insert ( transition.second ).second )
140 queue.push ( transition.second );
141 }
142
143 return closure;
144}
145
146template < class SymbolType, class StateType >
148 if ( ! fta.getStates ( ).contains ( q ) )
149 throw exception::CommonException ( "State is not in the automaton" );
150
152 std::queue < StateType > queue;
153 queue.push ( q );
154
155 while ( ! queue.empty ( ) ) {
156 StateType p = std::move ( queue.front ( ) );
157 queue.pop ( );
158
159 auto tos = fta.getTransitions ( ).equal_range ( p );
160 for ( const auto & transition : tos )
161 if ( closure.insert ( transition.second ).second )
162 queue.push ( transition.second );
163 }
164
165 return closure;
166}
167
168template < class T >
169requires isDFA < T > || isNFA < T > || isMultiInitialStateNFA < T >
171 if ( ! fsm.getStates ( ).contains ( q ) )
172 throw exception::CommonException ( "State is not in the automaton" );
173
174 return { q };
175}
176
177template < class SymbolType, class StateType >
179 if ( ! fsm.getStates ( ).contains ( q ) )
180 throw exception::CommonException("State is not in the automaton");
181
183 std::queue < StateType > queue;
184
185 queue.push ( q );
186 while ( ! queue.empty( ) ) {
187 StateType p = std::move ( queue.front ( ) );
188 queue.pop ( );
189
190 for ( const auto & transition : fsm.getTransitionsFromState ( p ) )
191 if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( transition.first.second ) )
192 if ( closure.insert ( transition.second ).second )
193 queue.push ( transition.second );
194 }
195
196 return closure;
197}
198
199template < class SymbolType, class StateType >
201 if ( ! fsm.getStates ( ).contains ( q ) )
202 throw exception::CommonException ("State is not in the automaton");
203
205 std::queue < StateType > queue;
206
207 queue.push ( q );
208 while ( ! queue.empty ( ) ) {
209 StateType p = std::move ( queue.front ( ) );
210 queue.pop ( );
211
212 for ( const auto & transition : fsm.getTransitionsFromState ( p ) )
213 if ( transition.first.second.empty ( ) )
214 if ( closure.insert ( transition.second ).second )
215 queue.push ( transition.second );
216 }
217
218 return closure;
219}
220
221} /* namespace properties */
222
223} /* namespace automaton */
Compact nondeterministic finite automaton. Accepts regular languages. The automaton has a list of sym...
Definition: CompactNFA.h:78
const ext::set< StateType > & getStates() const &
Definition: CompactNFA.h:183
ext::multimap< ext::pair< StateType, ext::vector< SymbolType > >, StateType > getTransitionsFromState(const StateType &from) const
Definition: CompactNFA.h:565
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
const ext::set< StateType > & getStates() const &
Definition: EpsilonNFA.h:158
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > & getTransitions() const &
Definition: EpsilonNFA.h:666
Epsilon nondeterministic finite tree automaton. Accepts regular tree languages.
Definition: EpsilonNFTA.h:73
const ext::set< StateType > & getStates() const &
Definition: EpsilonNFTA.h:118
const ext::multimap< ext::variant< StateType, ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > > >, StateType > & getTransitions() const &
Definition: EpsilonNFTA.h:354
Extended nondeterministic finite automaton. Accepts regular languages. The automaton has a regular ex...
Definition: ExtendedNFA.h:80
const ext::set< StateType > & getStates() const &
Definition: ExtendedNFA.h:185
ext::multimap< ext::pair< StateType, regexp::UnboundedRegExpStructure< SymbolType > >, StateType > getTransitionsFromState(const StateType &from) const
Definition: ExtendedNFA.h:591
Definition: EpsilonClosure.h:50
static ext::set< StateType > epsilonClosure(const automaton::EpsilonNFA< SymbolType, StateType > &fsm, const StateType &q)
Definition: EpsilonClosure.h:125
static ext::set< typename T::StateType > epsilonClosure(const T &fsm, const typename T::StateType &q)
Definition: symbol_or_epsilon.hpp:24
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
Definition: set.hpp:44
static bool languageContainsEpsilon(const regexp::FormalRegExpElement< SymbolType > &regexp)
Definition: RegExpEpsilon.h:91
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
return closure
Definition: AllEpsilonClosure.h:142
q
Definition: SingleInitialStateEpsilonTransition.h:85
Definition: ToGrammar.h:31
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79