Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
AutomatonCompare.h
Go to the documentation of this file.
1
6#pragma once
7
8#include "automaton/FSM/DFA.h"
9#include "automaton/FSM/NFA.h"
10#include "automaton/FSM/MultiInitialStateNFA.h"
11#include "automaton/FSM/EpsilonNFA.h"
12#include "automaton/FSM/ExtendedNFA.h"
13#include "automaton/FSM/CompactNFA.h"
14#include "automaton/FSM/CompactDFA.h"
15#include "automaton/TA/DFTA.h"
16#include "automaton/TA/NFTA.h"
17#include "automaton/PDA/NPDA.h"
18#include "automaton/PDA/DPDA.h"
19#include "automaton/PDA/InputDrivenNPDA.h"
20#include "automaton/PDA/InputDrivenDPDA.h"
21#include "automaton/PDA/VisiblyPushdownNPDA.h"
22#include "automaton/PDA/VisiblyPushdownDPDA.h"
23#include "automaton/PDA/RealTimeHeightDeterministicNPDA.h"
24#include "automaton/PDA/RealTimeHeightDeterministicDPDA.h"
25#include "automaton/PDA/SinglePopNPDA.h"
26#include "automaton/PDA/SinglePopDPDA.h"
27#include "automaton/TM/OneTapeDTM.h"
28
29namespace compare {
30
31class AutomatonCompare {
32public:
33 template<class SymbolType, class StateType>
34 static bool compare(const automaton::DFA < SymbolType, StateType > & a, const automaton::DFA < SymbolType, StateType > & b);
35
36 template<class SymbolType, class StateType>
37 static bool compare(const automaton::NFA < SymbolType, StateType > & a, const automaton::NFA < SymbolType, StateType > & b);
38
39 template<class SymbolType, class StateType>
40 static bool compare(const automaton::MultiInitialStateNFA < SymbolType, StateType > & a, const automaton::MultiInitialStateNFA < SymbolType, StateType > & b);
41
42 template<class SymbolType, class StateType>
43 static bool compare(const automaton::EpsilonNFA < SymbolType, StateType > & a, const automaton::EpsilonNFA < SymbolType, StateType > & b);
44
45 template<class SymbolType, class StateType>
46 static bool compare(const automaton::ExtendedNFA < SymbolType, StateType > & a, const automaton::ExtendedNFA < SymbolType, StateType > & b);
47
48 template<class SymbolType, class StateType>
49 static bool compare(const automaton::CompactDFA < SymbolType, StateType > & a, const automaton::CompactDFA < SymbolType, StateType > & b);
50
51 template<class SymbolType, class StateType>
52 static bool compare(const automaton::CompactNFA < SymbolType, StateType > & a, const automaton::CompactNFA < SymbolType, StateType > & b);
53
54 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
55 static bool compare(const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
56
57 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
58 static bool compare(const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
59
60 template<class SymbolType, class StateType>
61 static bool compare(const automaton::DFTA < SymbolType, StateType > & a, const automaton::DFTA < SymbolType, StateType > & b);
62
63 template<class SymbolType, class StateType>
64 static bool compare(const automaton::NFTA < SymbolType, StateType > & a, const automaton::NFTA < SymbolType, StateType > & b);
65
66 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
67 static bool compare(const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
68
69 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
70 static bool compare(const automaton::InputDrivenNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::InputDrivenNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
71
72 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
73 static bool compare(const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
74
75 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
76 static bool compare(const automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
77
78 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
79 static bool compare(const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
80
81 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
82 static bool compare(const automaton::RealTimeHeightDeterministicNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::RealTimeHeightDeterministicNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
83
84 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
85 static bool compare(const automaton::SinglePopDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::SinglePopDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
86
87 template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
88 static bool compare(const automaton::SinglePopNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::SinglePopNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b);
89
90 template<class SymbolType, class StateType>
91 static bool compare(const automaton::OneTapeDTM < SymbolType, StateType > & a, const automaton::OneTapeDTM < SymbolType, StateType > & b);
92};
93
94template<class SymbolType, class StateType>
95bool AutomatonCompare::compare(const automaton::DFA < SymbolType, StateType > & a, const automaton::DFA < SymbolType, StateType > & b) {
96 return a.getFinalStates() == b.getFinalStates() &&
97 a.getInitialState() == b.getInitialState() &&
98// a.getInputAlphabet() == b.getInputAlphabet() &&
99 a.getStates() == b.getStates() &&
100 a.getTransitions() == b.getTransitions() ;
101}
102
103template<class SymbolType, class StateType>
104bool AutomatonCompare::compare(const automaton::MultiInitialStateNFA < SymbolType, StateType > & a, const automaton::MultiInitialStateNFA < SymbolType, StateType > & b) {
105 return a.getFinalStates() == b.getFinalStates() &&
106 a.getInitialStates() == b.getInitialStates() &&
107// a.getInputAlphabet() == b.getInputAlphabet() &&
108 a.getStates() == b.getStates() &&
109 a.getTransitions() == b.getTransitions() ;
110}
111
112template<class SymbolType, class StateType>
113bool AutomatonCompare::compare(const automaton::NFA < SymbolType, StateType > & a, const automaton::NFA < SymbolType, StateType > & b) {
114 return a.getFinalStates() == b.getFinalStates() &&
115 a.getInitialState() == b.getInitialState() &&
116// a.getInputAlphabet() == b.getInputAlphabet() &&
117 a.getStates() == b.getStates() &&
118 a.getTransitions() == b.getTransitions() ;
119}
120
121template<class SymbolType, class StateType>
122bool AutomatonCompare::compare(const automaton::EpsilonNFA < SymbolType, StateType > & a, const automaton::EpsilonNFA < SymbolType, StateType > & b) {
123 return a.getFinalStates() == b.getFinalStates() &&
124 a.getInitialState() == b.getInitialState() &&
125// a.getInputAlphabet() == b.getInputAlphabet() &&
126 a.getStates() == b.getStates() &&
127 a.getTransitions() == b.getTransitions() ;
128}
129
130template<class SymbolType, class StateType>
131bool AutomatonCompare::compare(const automaton::ExtendedNFA < SymbolType, StateType > & a, const automaton::ExtendedNFA < SymbolType, StateType > & b) {
132 return a.getFinalStates() == b.getFinalStates() &&
133 a.getInitialState() == b.getInitialState() &&
134// a.getInputAlphabet() == b.getInputAlphabet() &&
135 a.getStates() == b.getStates() &&
136 a.getTransitions() == b.getTransitions() ;
137}
138
139template<class SymbolType, class StateType>
140bool AutomatonCompare::compare(const automaton::CompactDFA < SymbolType, StateType > & a, const automaton::CompactDFA < SymbolType, StateType > & b) {
141 return a.getFinalStates() == b.getFinalStates() &&
142 a.getInitialState() == b.getInitialState() &&
143// a.getInputAlphabet() == b.getInputAlphabet() &&
144 a.getStates() == b.getStates() &&
145 a.getTransitions() == b.getTransitions() ;
146}
147
148template<class SymbolType, class StateType>
149bool AutomatonCompare::compare(const automaton::CompactNFA < SymbolType, StateType > & a, const automaton::CompactNFA < SymbolType, StateType > & b) {
150 return a.getFinalStates() == b.getFinalStates() &&
151 a.getInitialState() == b.getInitialState() &&
152// a.getInputAlphabet() == b.getInputAlphabet() &&
153 a.getStates() == b.getStates() &&
154 a.getTransitions() == b.getTransitions() ;
155}
156
157template<class SymbolType, class StateType>
158bool AutomatonCompare::compare(const automaton::DFTA < SymbolType, StateType > & a, const automaton::DFTA < SymbolType, StateType > & b) {
159 return a.getFinalStates() == b.getFinalStates() &&
160// a.getInputAlphabet() == b.getInputAlphabet() &&
161 a.getStates() == b.getStates() &&
162 a.getTransitions() == b.getTransitions() ;
163}
164
165template<class SymbolType, class StateType>
166bool AutomatonCompare::compare(const automaton::NFTA < SymbolType, StateType > & a, const automaton::NFTA < SymbolType, StateType > & b) {
167 return a.getFinalStates() == b.getFinalStates() &&
168// a.getInputAlphabet() == b.getInputAlphabet() &&
169 a.getStates() == b.getStates() &&
170 a.getTransitions() == b.getTransitions() ;
171}
172
173template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
174bool AutomatonCompare::compare(const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
175 return a.getFinalStates() == b.getFinalStates() &&
176 a.getInitialState() == b.getInitialState() &&
177// a.getInputAlphabet() == b.getInputAlphabet() &&
178// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
179 a.getInitialSymbol() == b.getInitialSymbol() &&
180 a.getStates() == b.getStates() &&
181 a.getTransitions() == b.getTransitions() ;
182}
183
184template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
185bool AutomatonCompare::compare(const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
186 return a.getFinalStates() == b.getFinalStates() &&
187 a.getInitialState() == b.getInitialState() &&
188// a.getInputAlphabet() == b.getInputAlphabet() &&
189// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
190 a.getInitialSymbol() == b.getInitialSymbol() &&
191 a.getStates() == b.getStates() &&
192 a.getTransitions() == b.getTransitions() ;
193}
194
195template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
196bool AutomatonCompare::compare(const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
197 return a.getFinalStates() == b.getFinalStates() &&
198 a.getInitialState() == b.getInitialState() &&
199// a.getInputAlphabet() == b.getInputAlphabet() &&
200// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
201 a.getInitialSymbol() == b.getInitialSymbol() &&
202 a.getStates() == b.getStates() &&
203 a.getPushdownStoreOperations() == b.getPushdownStoreOperations() &&
204 a.getTransitions() == b.getTransitions() ;
205}
206
207template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
208bool AutomatonCompare::compare(const automaton::InputDrivenNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::InputDrivenNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
209 return a.getFinalStates() == b.getFinalStates() &&
210 a.getInitialState() == b.getInitialState() &&
211// a.getInputAlphabet() == b.getInputAlphabet() &&
212// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
213 a.getInitialSymbol() == b.getInitialSymbol() &&
214 a.getStates() == b.getStates() &&
215 a.getPushdownStoreOperations() == b.getPushdownStoreOperations() &&
216 a.getTransitions() == b.getTransitions() ;
217}
218
219template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
220bool AutomatonCompare::compare(const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
221 return a.getFinalStates() == b.getFinalStates() &&
222 a.getInitialState() == b.getInitialState() &&
223// a.getCallInputAlphabet() == b.getCallInputAlphabet() &&
224// a.getReturnnputAlphabet() == b.getReturnInputAlphabet() &&
225// a.getLocalInputAlphabet() == b.getLocalInputAlphabet() &&
226// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
227 a.getBottomOfTheStackSymbol() == b.getBottomOfTheStackSymbol() &&
228 a.getStates() == b.getStates() &&
229 a.getCallTransitions() == b.getCallTransitions() &&
230 a.getReturnTransitions() == b.getReturnTransitions() &&
231 a.getLocalTransitions() == b.getLocalTransitions() ;
232}
233
234template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
235bool AutomatonCompare::compare(const automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
236 return a.getFinalStates() == b.getFinalStates() &&
237 a.getInitialStates() == b.getInitialStates() &&
238// a.getCallInputAlphabet() == b.getCallInputAlphabet() &&
239// a.getReturnnputAlphabet() == b.getReturnInputAlphabet() &&
240// a.getLocalInputAlphabet() == b.getLocalInputAlphabet() &&
241// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
242 a.getBottomOfTheStackSymbol() == b.getBottomOfTheStackSymbol() &&
243 a.getStates() == b.getStates() &&
244 a.getCallTransitions() == b.getCallTransitions() &&
245 a.getReturnTransitions() == b.getReturnTransitions() &&
246 a.getLocalTransitions() == b.getLocalTransitions() ;
247}
248
249template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
250bool AutomatonCompare::compare(const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
251 return a.getFinalStates() == b.getFinalStates() &&
252 a.getInitialState() == b.getInitialState() &&
253// a.getInputAlphabet() == b.getInputAlphabet() &&
254// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
255 a.getBottomOfTheStackSymbol() == b.getBottomOfTheStackSymbol() &&
256 a.getStates() == b.getStates() &&
257 a.getCallTransitions() == b.getCallTransitions() &&
258 a.getReturnTransitions() == b.getReturnTransitions() &&
259 a.getLocalTransitions() == b.getLocalTransitions() ;
260}
261
262template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
263bool AutomatonCompare::compare(const automaton::RealTimeHeightDeterministicNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::RealTimeHeightDeterministicNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
264 return a.getFinalStates() == b.getFinalStates() &&
265 a.getInitialStates() == b.getInitialStates() &&
266// a.getInputAlphabet() == b.getInputAlphabet() &&
267// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
268 a.getBottomOfTheStackSymbol() == b.getBottomOfTheStackSymbol() &&
269 a.getStates() == b.getStates() &&
270 a.getCallTransitions() == b.getCallTransitions() &&
271 a.getReturnTransitions() == b.getReturnTransitions() &&
272 a.getLocalTransitions() == b.getLocalTransitions() ;
273}
274
275template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
276bool AutomatonCompare::compare(const automaton::SinglePopDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::SinglePopDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
277 return a.getFinalStates() == b.getFinalStates() &&
278 a.getInitialState() == b.getInitialState() &&
279// a.getInputAlphabet() == b.getInputAlphabet() &&
280// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
281 a.getInitialSymbol() == b.getInitialSymbol() &&
282 a.getStates() == b.getStates() &&
283 a.getTransitions() == b.getTransitions() ;
284}
285
286template<class InputSymbolType, class PushdownStoreSymbolType, class StateType>
287bool AutomatonCompare::compare(const automaton::SinglePopNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & a, const automaton::SinglePopNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & b) {
288 return a.getFinalStates() == b.getFinalStates() &&
289 a.getInitialState() == b.getInitialState() &&
290// a.getInputAlphabet() == b.getInputAlphabet() &&
291// a.getPushdownStoreAlphabet() == b.getPushdownStoreAlphabet() &&
292 a.getInitialSymbol() == b.getInitialSymbol() &&
293 a.getStates() == b.getStates() &&
294 a.getTransitions() == b.getTransitions() ;
295}
296
297template<class SymbolType, class StateType>
298bool AutomatonCompare::compare(const automaton::OneTapeDTM < SymbolType, StateType > & a, const automaton::OneTapeDTM < SymbolType, StateType > & b) {
299 return a.getBlankSymbol() == b.getBlankSymbol() &&
300 a.getFinalStates() == b.getFinalStates() &&
301 a.getInitialState() == b.getInitialState() &&
302// a.getInputAlphabet() == b.getInputAlphabet() &&
303 a.getStates() == b.getStates() &&
304// a.getTapeAlphabet() == b.getTapeAlphabet() &&
305 a.getTransitions() == b.getTransitions() ;
306}
307
308} /* namespace compare */
309
automaton::CompactDFA
Compact deterministic finite automaton. Accepts regular languages. The automaton has a list of symbol...
Definition: CompactDFA.h:73
automaton::CompactDFA::getTransitions
const ext::map< ext::pair< StateType, ext::vector< SymbolType > >, StateType > & getTransitions() const &
Definition: CompactDFA.h:483
automaton::CompactDFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: CompactDFA.h:192
automaton::CompactDFA::getInitialState
const StateType & getInitialState() const &
Definition: CompactDFA.h:114
automaton::CompactDFA::getStates
const ext::set< StateType > & getStates() const &
Definition: CompactDFA.h:143
automaton::CompactNFA
Compact nondeterministic finite automaton. Accepts regular languages. The automaton has a list of sym...
Definition: CompactNFA.h:78
automaton::CompactNFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: CompactNFA.h:232
automaton::CompactNFA::getTransitions
const ext::multimap< ext::pair< StateType, ext::vector< SymbolType > >, StateType > & getTransitions() const &
Definition: CompactNFA.h:555
automaton::CompactNFA::getStates
const ext::set< StateType > & getStates() const &
Definition: CompactNFA.h:183
automaton::CompactNFA::getInitialState
const StateType & getInitialState() const &
Definition: CompactNFA.h:154
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::getStates
const ext::set< StateType > & getStates() const &
Definition: DFA.h:134
automaton::DFTA
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
automaton::DFTA::getTransitions
const ext::map< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions() const &
Definition: DFTA.h:289
automaton::DFTA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: DFTA.h:154
automaton::DFTA::getStates
const ext::set< StateType > & getStates() const &
Definition: DFTA.h:105
automaton::DPDA
Deterministic pushdown automaton. Accepts subset of context free languages.
Definition: DPDA.h:78
automaton::DPDA::getInitialSymbol
const PushdownStoreSymbolType & getInitialSymbol() const &
Definition: DPDA.h:301
automaton::DPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: DPDA.h:145
automaton::DPDA::getTransitions
const ext::map< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, ext::vector< PushdownStoreSymbolType > >, ext::pair< StateType, ext::vector< PushdownStoreSymbolType > > > & getTransitions() const &
Definition: DPDA.h:682
automaton::DPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: DPDA.h:194
automaton::DPDA::getInitialState
const StateType & getInitialState() const &
Definition: DPDA.h:116
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::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: EpsilonNFA.h:207
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::ExtendedNFA
Extended nondeterministic finite automaton. Accepts regular languages. The automaton has a regular ex...
Definition: ExtendedNFA.h:80
automaton::ExtendedNFA::getInitialState
const StateType & getInitialState() const &
Definition: ExtendedNFA.h:156
automaton::ExtendedNFA::getTransitions
const ext::multimap< ext::pair< StateType, regexp::UnboundedRegExpStructure< SymbolType > >, StateType > & getTransitions() const &
Definition: ExtendedNFA.h:581
automaton::ExtendedNFA::getStates
const ext::set< StateType > & getStates() const &
Definition: ExtendedNFA.h:185
automaton::ExtendedNFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: ExtendedNFA.h:234
automaton::InputDrivenDPDA
Deterministic input driven pushdown automaton. Accepts subset of context free languages.
Definition: InputDrivenDPDA.h:79
automaton::InputDrivenDPDA::getTransitions
const ext::map< ext::pair< StateType, InputSymbolType >, StateType > & getTransitions() const &
Definition: InputDrivenDPDA.h:655
automaton::InputDrivenDPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: InputDrivenDPDA.h:160
automaton::InputDrivenDPDA::getInitialSymbol
const PushdownStoreSymbolType & getInitialSymbol() const &
Definition: InputDrivenDPDA.h:316
automaton::InputDrivenDPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: InputDrivenDPDA.h:209
automaton::InputDrivenDPDA::getPushdownStoreOperations
const ext::map< InputSymbolType, ext::pair< ext::vector< PushdownStoreSymbolType >, ext::vector< PushdownStoreSymbolType > > > & getPushdownStoreOperations() const &
Definition: InputDrivenDPDA.h:604
automaton::InputDrivenDPDA::getInitialState
const StateType & getInitialState() const &
Definition: InputDrivenDPDA.h:131
automaton::InputDrivenNPDA
Nondeterministic input driven pushdown automaton. Accepts subset of context free languages.
Definition: InputDrivenNPDA.h:79
automaton::InputDrivenNPDA::getInitialSymbol
const PushdownStoreSymbolType & getInitialSymbol() const &
Definition: InputDrivenNPDA.h:316
automaton::InputDrivenNPDA::getPushdownStoreOperations
const ext::map< InputSymbolType, ext::pair< ext::vector< PushdownStoreSymbolType >, ext::vector< PushdownStoreSymbolType > > > & getPushdownStoreOperations() const &
Definition: InputDrivenNPDA.h:614
automaton::InputDrivenNPDA::getTransitions
const ext::multimap< ext::pair< StateType, InputSymbolType >, StateType > & getTransitions() const &
Definition: InputDrivenNPDA.h:661
automaton::InputDrivenNPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: InputDrivenNPDA.h:209
automaton::InputDrivenNPDA::getInitialState
const StateType & getInitialState() const &
Definition: InputDrivenNPDA.h:131
automaton::InputDrivenNPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: InputDrivenNPDA.h:160
automaton::MultiInitialStateNFA
Nondeterministic finite automaton with multiple initial states. Accepts regular languages.
Definition: MultiInitialStateNFA.h:69
automaton::MultiInitialStateNFA::getInitialStates
const ext::set< StateType > & getInitialStates() const &
Definition: MultiInitialStateNFA.h:117
automaton::MultiInitialStateNFA::getStates
const ext::set< StateType > & getStates() const &
Definition: MultiInitialStateNFA.h:166
automaton::MultiInitialStateNFA::getTransitions
const ext::multimap< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: MultiInitialStateNFA.h:520
automaton::MultiInitialStateNFA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: MultiInitialStateNFA.h:215
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::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::NFTA
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
automaton::NFTA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: NFTA.h:159
automaton::NFTA::getTransitions
const ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions() const &
Definition: NFTA.h:294
automaton::NFTA::getStates
const ext::set< StateType > & getStates() const &
Definition: NFTA.h:110
automaton::NPDA
Definition: NPDA.h:74
automaton::NPDA::getInitialSymbol
const PushdownStoreSymbolType & getInitialSymbol() const &
Definition: NPDA.h:304
automaton::NPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: NPDA.h:197
automaton::NPDA::getInitialState
const StateType & getInitialState() const &
Definition: NPDA.h:119
automaton::NPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: NPDA.h:148
automaton::NPDA::getTransitions
const ext::multimap< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, ext::vector< PushdownStoreSymbolType > >, ext::pair< StateType, ext::vector< PushdownStoreSymbolType > > > & getTransitions() const &
Definition: NPDA.h:644
automaton::OneTapeDTM
Deterministic single tape turing machine. Accepts recursive languages.
Definition: OneTapeDTM.h:71
automaton::OneTapeDTM::getInitialState
const StateType & getInitialState() const &
Definition: OneTapeDTM.h:108
automaton::OneTapeDTM::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: OneTapeDTM.h:186
automaton::OneTapeDTM::getTransitions
const ext::map< ext::pair< StateType, SymbolType >, ext::tuple< StateType, SymbolType, Shift > > & getTransitions() const &
Definition: OneTapeDTM.h:526
automaton::OneTapeDTM::getBlankSymbol
const SymbolType & getBlankSymbol() const &
Definition: OneTapeDTM.h:351
automaton::OneTapeDTM::getStates
const ext::set< StateType > & getStates() const &
Definition: OneTapeDTM.h:137
automaton::RealTimeHeightDeterministicDPDA
Deterministic real time height deterministic pushdown automaton. Accepts subset of context free langu...
Definition: RealTimeHeightDeterministicDPDA.h:89
automaton::RealTimeHeightDeterministicDPDA::getInitialState
const StateType & getInitialState() const &
Definition: RealTimeHeightDeterministicDPDA.h:149
automaton::RealTimeHeightDeterministicDPDA::getCallTransitions
const ext::map< ext::pair< StateType, common::symbol_or_epsilon< InputSymbolType > >, ext::pair< StateType, PushdownStoreSymbolType > > & getCallTransitions() const &
Definition: RealTimeHeightDeterministicDPDA.h:1062
automaton::RealTimeHeightDeterministicDPDA::getLocalTransitions
const ext::map< ext::pair< StateType, common::symbol_or_epsilon< InputSymbolType > >, StateType > & getLocalTransitions() const &
Definition: RealTimeHeightDeterministicDPDA.h:1082
automaton::RealTimeHeightDeterministicDPDA::getReturnTransitions
const ext::map< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, PushdownStoreSymbolType >, StateType > & getReturnTransitions() const &
Definition: RealTimeHeightDeterministicDPDA.h:1072
automaton::RealTimeHeightDeterministicDPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: RealTimeHeightDeterministicDPDA.h:178
automaton::RealTimeHeightDeterministicDPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: RealTimeHeightDeterministicDPDA.h:227
automaton::RealTimeHeightDeterministicDPDA::getBottomOfTheStackSymbol
const PushdownStoreSymbolType & getBottomOfTheStackSymbol() const &
Definition: RealTimeHeightDeterministicDPDA.h:334
automaton::RealTimeHeightDeterministicNPDA
Nondeterministic real time height deterministic pushdown automaton. Accepts subset of context free la...
Definition: RealTimeHeightDeterministicNPDA.h:76
automaton::RealTimeHeightDeterministicNPDA::getInitialStates
const ext::set< StateType > & getInitialStates() const &
Definition: RealTimeHeightDeterministicNPDA.h:175
automaton::RealTimeHeightDeterministicNPDA::getBottomOfTheStackSymbol
const PushdownStoreSymbolType & getBottomOfTheStackSymbol() const &
Definition: RealTimeHeightDeterministicNPDA.h:331
automaton::RealTimeHeightDeterministicNPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: RealTimeHeightDeterministicNPDA.h:126
automaton::RealTimeHeightDeterministicNPDA::getLocalTransitions
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< InputSymbolType > >, StateType > & getLocalTransitions() const &
Definition: RealTimeHeightDeterministicNPDA.h:1004
automaton::RealTimeHeightDeterministicNPDA::getCallTransitions
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< InputSymbolType > >, ext::pair< StateType, PushdownStoreSymbolType > > & getCallTransitions() const &
Definition: RealTimeHeightDeterministicNPDA.h:984
automaton::RealTimeHeightDeterministicNPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: RealTimeHeightDeterministicNPDA.h:224
automaton::RealTimeHeightDeterministicNPDA::getReturnTransitions
const ext::multimap< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, PushdownStoreSymbolType >, StateType > & getReturnTransitions() const &
Definition: RealTimeHeightDeterministicNPDA.h:994
automaton::SinglePopDPDA
Deterministic pushdown automaton requiring a symbol pop from pushdown store on each transition use....
Definition: SinglePopDPDA.h:78
automaton::SinglePopDPDA::getInitialState
const StateType & getInitialState() const &
Definition: SinglePopDPDA.h:116
automaton::SinglePopDPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: SinglePopDPDA.h:194
automaton::SinglePopDPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: SinglePopDPDA.h:145
automaton::SinglePopDPDA::getInitialSymbol
const PushdownStoreSymbolType & getInitialSymbol() const &
Definition: SinglePopDPDA.h:301
automaton::SinglePopDPDA::getTransitions
const ext::map< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, PushdownStoreSymbolType >, ext::pair< StateType, ext::vector< PushdownStoreSymbolType > > > & getTransitions() const &
Definition: SinglePopDPDA.h:639
automaton::SinglePopNPDA
Definition: SinglePopNPDA.h:72
automaton::SinglePopNPDA::getInitialState
const StateType & getInitialState() const &
Definition: SinglePopNPDA.h:110
automaton::SinglePopNPDA::getInitialSymbol
const PushdownStoreSymbolType & getInitialSymbol() const &
Definition: SinglePopNPDA.h:295
automaton::SinglePopNPDA::getTransitions
const ext::multimap< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, PushdownStoreSymbolType >, ext::pair< StateType, ext::vector< PushdownStoreSymbolType > > > & getTransitions() const &
Definition: SinglePopNPDA.h:617
automaton::SinglePopNPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: SinglePopNPDA.h:139
automaton::SinglePopNPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: SinglePopNPDA.h:188
automaton::VisiblyPushdownDPDA
Deterministic visibly pushdown automaton. Accepts subset of context free languages.
Definition: VisiblyPushdownDPDA.h:86
automaton::VisiblyPushdownDPDA::getBottomOfTheStackSymbol
const PushdownStoreSymbolType & getBottomOfTheStackSymbol() const &
Definition: VisiblyPushdownDPDA.h:331
automaton::VisiblyPushdownDPDA::getReturnTransitions
const ext::map< ext::tuple< StateType, InputSymbolType, PushdownStoreSymbolType >, StateType > & getReturnTransitions() const &
Definition: VisiblyPushdownDPDA.h:899
automaton::VisiblyPushdownDPDA::getLocalTransitions
const ext::map< ext::pair< StateType, InputSymbolType >, StateType > & getLocalTransitions() const &
Definition: VisiblyPushdownDPDA.h:909
automaton::VisiblyPushdownDPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: VisiblyPushdownDPDA.h:224
automaton::VisiblyPushdownDPDA::getCallTransitions
const ext::map< ext::pair< StateType, InputSymbolType >, ext::pair< StateType, PushdownStoreSymbolType > > & getCallTransitions() const &
Definition: VisiblyPushdownDPDA.h:889
automaton::VisiblyPushdownDPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: VisiblyPushdownDPDA.h:175
automaton::VisiblyPushdownDPDA::getInitialState
const StateType & getInitialState() const &
Definition: VisiblyPushdownDPDA.h:146
automaton::VisiblyPushdownNPDA
Nondeterministic visibly pushdown automaton. Accepts subset of context free languages.
Definition: VisiblyPushdownNPDA.h:81
automaton::VisiblyPushdownNPDA::getBottomOfTheStackSymbol
const PushdownStoreSymbolType & getBottomOfTheStackSymbol() const &
Definition: VisiblyPushdownNPDA.h:336
automaton::VisiblyPushdownNPDA::getInitialStates
const ext::set< StateType > & getInitialStates() const &
Definition: VisiblyPushdownNPDA.h:131
automaton::VisiblyPushdownNPDA::getStates
const ext::set< StateType > & getStates() const &
Definition: VisiblyPushdownNPDA.h:180
automaton::VisiblyPushdownNPDA::getLocalTransitions
const ext::multimap< ext::pair< StateType, InputSymbolType >, StateType > & getLocalTransitions() const &
Definition: VisiblyPushdownNPDA.h:884
automaton::VisiblyPushdownNPDA::getFinalStates
const ext::set< StateType > & getFinalStates() const &
Definition: VisiblyPushdownNPDA.h:229
automaton::VisiblyPushdownNPDA::getReturnTransitions
const ext::multimap< ext::tuple< StateType, InputSymbolType, PushdownStoreSymbolType >, StateType > & getReturnTransitions() const &
Definition: VisiblyPushdownNPDA.h:874
automaton::VisiblyPushdownNPDA::getCallTransitions
const ext::multimap< ext::pair< StateType, InputSymbolType >, ext::pair< StateType, PushdownStoreSymbolType > > & getCallTransitions() const &
Definition: VisiblyPushdownNPDA.h:864
compare::AutomatonCompare
Definition: AutomatonCompare.h:31
compare::AutomatonCompare::compare
static bool compare(const automaton::DFA< SymbolType, StateType > &a, const automaton::DFA< SymbolType, StateType > &b)
Definition: AutomatonCompare.h:95
compare
Definition: AutomatonCompare.h:29
Generated on Mon Dec 27 2021 10:21:52 for Algorithms Library Toolkit by doxygen 1.9.2