Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
Accept.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <string/LinearString.h>
9#include <tree/ranked/RankedTree.h>
10
11#include "Run.h"
12#include <automaton/FSM/DFA.h>
13#include <automaton/FSM/NFA.h>
14#include <automaton/TA/DFTA.h>
15#include <automaton/TA/NFTA.h>
16#include <automaton/PDA/InputDrivenDPDA.h>
17#include <automaton/PDA/VisiblyPushdownDPDA.h>
18#include <automaton/PDA/RealTimeHeightDeterministicDPDA.h>
19#include <automaton/PDA/DPDA.h>
20#include <automaton/PDA/NPDTA.h>
21
22#include <ext/algorithm>
23
24#include <alib/deque>
25#include <alib/vector>
26
27namespace automaton {
28
29namespace run {
30
35class Accept {
36public:
48 template < class SymbolType, class StateType >
49 static bool accept ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
50
62 template < class SymbolType, class StateType >
63 static bool accept ( const automaton::NFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
64
76 template < class SymbolType, class StateType >
77 static bool accept ( const automaton::EpsilonNFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
78
91 template < class SymbolType, class StateType >
92 static bool accept ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree );
93
94 template < class SymbolType, class StateType >
95 static bool accept ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree );
96
109 template < class SymbolType, class StateType >
110 static bool accept ( const automaton::NFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree );
111
124 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
125 static bool accept ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
126
139 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
140 static bool accept ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
141
154 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
155 static bool accept ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
156
169 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
170 static bool accept ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
171
184 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
185 static bool accept ( const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
186
200 template < class InputSymbolType, class OutputSymbolType, class PushdownStoreSymbolType, class StateType >
201 static bool accept ( const automaton::NPDTA < InputSymbolType, OutputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
202
203};
204
205template < class SymbolType, class StateType >
206bool Accept::accept ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
207 ext::tuple < bool, StateType, ext::set < unsigned > > res = Run::calculateState ( automaton, string );
208
209 return std::get < 0 > ( res ) && automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) );
210}
211
212template < class SymbolType, class StateType >
213bool Accept::accept ( const automaton::NFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
214 ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > res = Run::calculateStates ( automaton, string );
215
216 return std::get < 0 > ( res ) && std::any_of ( std::get < 1 > ( res ).begin ( ), std::get < 1 > ( res ).end ( ), [&] ( const StateType & state ) {
217 return automaton.getFinalStates ( ).count ( state );
218 } );
219}
220
221template < class SymbolType, class StateType >
222bool Accept::accept ( const automaton::EpsilonNFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
223 ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > res = Run::calculateStates ( automaton, string );
224
225 return std::get < 0 > ( res ) && std::any_of ( std::get < 1 > ( res ).begin ( ), std::get < 1 > ( res ).end ( ), [&] ( const StateType & state ) {
226 return automaton.getFinalStates ( ).count ( state );
227 } );
228}
229
230template < class SymbolType, class StateType >
231bool Accept::accept ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree ) {
232 ext::tuple < bool, StateType, ext::set < unsigned > > res = Run::calculateState ( automaton, tree );
233
234 return std::get < 0 > ( res ) && automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) );
235}
236
237template < class SymbolType, class StateType >
238bool Accept::accept ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree ) {
239 ext::tuple < bool, StateType, ext::set < unsigned > > res = Run::calculateState ( automaton, tree );
240
241 return std::get < 0 > ( res ) && automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) );
242}
243
244template < class SymbolType, class StateType >
245bool Accept::accept ( const automaton::NFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree ) {
246 ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > res = Run::calculateStates ( automaton, tree );
247
248 return std::get < 0 > ( res ) && std::any_of ( std::get < 1 > ( res ).begin ( ), std::get < 1 > ( res ).end ( ), [&] ( const StateType & state ) {
249 return automaton.getFinalStates ( ).count ( state );
250 } );
251}
252
253template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
254bool Accept::accept ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
255 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
256
257 return std::get < 0 > ( res ) && ( automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) ) || ( automaton.getFinalStates ( ).empty ( ) && std::get < 3 > ( res ).empty ( ) ) );
258}
259
260template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
261bool Accept::accept ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
262 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
263
264 return std::get < 0 > ( res ) && automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) );
265}
266
267template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
268bool Accept::accept ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
269 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
270
271 return std::get < 0 > ( res ) && automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) );
272}
273
274template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
275bool Accept::accept ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
276 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
277
278 return std::get < 0 > ( res ) && ( automaton.getFinalStates ( ).count ( std::get < 1 > ( res ) ) || ( automaton.getFinalStates ( ).empty ( ) && std::get < 3 > ( res ).empty ( ) ) );
279}
280
281template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
282bool Accept::accept ( const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
283 ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > > res = Run::calculateStates ( automaton, string );
284
285 for ( const ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > & finalConfiguration : res )
286 if ( automaton.getFinalStates ( ).contains ( std::get < 0 > ( finalConfiguration ) ) || ( automaton.getFinalStates ( ).empty ( ) && std::get < 2 > ( finalConfiguration ).empty ( ) ) )
287 return true;
288
289 return false;
290}
291
292template < class InputSymbolType, class OutputSymbolType, class PushdownStoreSymbolType, class StateType >
293bool Accept::accept ( const automaton::NPDTA < InputSymbolType, OutputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
294 ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType >, ext::deque < OutputSymbolType > > > res = Run::calculateStates ( automaton, string );
295
296 for ( const ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType >, ext::deque < OutputSymbolType > > & finalConfiguration : res )
297 if ( automaton.getFinalStates ( ).contains ( std::get < 0 > ( finalConfiguration ) ) || ( automaton.getFinalStates ( ).empty ( ) && std::get < 2 > ( finalConfiguration ).empty ( ) ) )
298 return true;
299
300 return false;
301}
302
303} /* namespace run */
304
305} /* namespace automaton */
306
automaton::ArcFactoredDeterministicZAutomaton
Deterministic Z-Automaton in Arc-Factored Normal Form. Computation model for unranked regular tree la...
Definition: ArcFactoredDeterministicZAutomaton.h:65
automaton::DFA
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
automaton::DFTA
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
automaton::DPDA
Deterministic pushdown automaton. Accepts subset of context free languages.
Definition: DPDA.h:78
automaton::EpsilonNFA
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
automaton::InputDrivenDPDA
Deterministic input driven pushdown automaton. Accepts subset of context free languages.
Definition: InputDrivenDPDA.h:79
automaton::NFA
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
automaton::NFTA
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
automaton::NPDA
Definition: NPDA.h:74
automaton::NPDTA
Definition: NPDTA.h:75
automaton::RealTimeHeightDeterministicDPDA
Deterministic real time height deterministic pushdown automaton. Accepts subset of context free langu...
Definition: RealTimeHeightDeterministicDPDA.h:89
automaton::VisiblyPushdownDPDA
Deterministic visibly pushdown automaton. Accepts subset of context free languages.
Definition: VisiblyPushdownDPDA.h:86
automaton::run::Accept
Implementation of test whether automaton accepts its input.
Definition: Accept.h:35
automaton::run::Accept::accept
static bool accept(const automaton::DFA< SymbolType, StateType > &automaton, const string::LinearString< SymbolType > &string)
Definition: Accept.h:206
ext::deque
Class extending the deque class from the standard library. Original reason is to allow printing of th...
Definition: deque.hpp:44
ext::set
Definition: set.hpp:44
ext::tuple
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
string::LinearString
Linear string.
Definition: LinearString.h:57
tree::RankedTree
Tree structure represented in its natural representation. The representation is so called ranked,...
Definition: RankedTree.h:72
tree::UnrankedTree
Tree represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedTree.h:69
automaton::convert::StateType
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
automaton
Definition: ToGrammar.h:31
ext::any_of
any_of(T &&...) -> any_of< T... >
ext::begin
auto begin(Container &&cont) -> decltype(std::forward(cont).begin())
Definition: iterator.hpp:900
measurements::end
void end()
Definition: measurements.cpp:19
tree
Definition: BackwardOccurrenceTest.h:17
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2