Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*
* AutomatonPropertiesFSM.cpp
*
* Created on: 23. 3. 2014
* Author: Tomas Pecka
*/
#include "AutomatonPropertiesFSM.h"
#include <exception/AlibException.h>
#include <automaton/FSM/ExtendedNFA.h>
#include <automaton/FSM/CompactNFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>
namespace automaton {
template<class T>
std::set<automaton::State> AutomatonPropertiesFSM::getUsefullStates( const T & fsm ) {
// 1a
std::deque<std::set<automaton::State>> Qi;
Qi.push_back( std::set<automaton::State>( ) );
Qi.at( 0 ) = fsm.getFinalStates( );
int i = 1;
// 1bc
while( true ) {
Qi.push_back( Qi.at( i - 1 ) ); // copy Qi-1 into Qi
for( const auto & p : Qi.at( i - 1 ) )
for( const auto & t : fsm.getTransitionsToState( p ) )
Qi.at( i ).insert( t.first.first );
if( Qi.at( i ) == Qi.at( i - 1 ) )
break;
i = i + 1;
}
return Qi.at( i );
}
template std::set<automaton::State> AutomatonPropertiesFSM::getUsefullStates( const automaton::EpsilonNFA & fsm );
template std::set<automaton::State> AutomatonPropertiesFSM::getUsefullStates( const automaton::NFA & fsm );
template std::set<automaton::State> AutomatonPropertiesFSM::getUsefullStates( const automaton::CompactNFA & fsm );
template std::set<automaton::State> AutomatonPropertiesFSM::getUsefullStates( const automaton::ExtendedNFA & fsm );
template<>
std::set<automaton::State> AutomatonPropertiesFSM::getUsefullStates( const automaton::DFA & fsm ) {
// 1a
std::deque<std::set<automaton::State>> Qi;
Qi.push_back( std::set<automaton::State>( ) );
Qi.at( 0 ) = fsm.getFinalStates( );
int i = 1;
// 1bc
while( true ) {
Qi.push_back( Qi.at( i - 1 ) ); // copy Qi-1 into Qi
for( const auto & p : Qi.at( i - 1 ) )
for( const auto & t : fsm.getTransitionsToState( p ) )
Qi.at( i ).insert( t.first.first );
if( Qi.at( i ) == Qi.at( i - 1 ) )
break;
i = i + 1;
}
return Qi.at( i );
}
template<class T>
std::set<automaton::State> AutomatonPropertiesFSM::getUnreachableStates( const T & fsm ) {
// 1a
std::deque<std::set<automaton::State>> Qi;
Qi.push_back( std::set<automaton::State>( ) );
Qi.at( 0 ) = fsm.getInitialStates( );
int i = 1;
// 1bc
while( true ) {
Qi.push_back( Qi.at( i - 1 ) );
for( const auto & p : Qi.at( i - 1 ) )
for( const auto & transition : fsm.getTransitionsFromState( p ) )
Qi.at( i ).insert( transition.second.begin(), transition.second.end() );
if( Qi.at( i ) == Qi.at( i - 1 ) )
break;
i = i + 1;
}
return Qi.at( i );
}
template std::set<automaton::State> AutomatonPropertiesFSM::getUnreachableStates( const automaton::EpsilonNFA & fsm );
template std::set<automaton::State> AutomatonPropertiesFSM::getUnreachableStates( const automaton::NFA & fsm );
template std::set<automaton::State> AutomatonPropertiesFSM::getUnreachableStates( const automaton::CompactNFA & fsm );
template std::set<automaton::State> AutomatonPropertiesFSM::getUnreachableStates( const automaton::ExtendedNFA & fsm );
template<>
std::set<automaton::State> AutomatonPropertiesFSM::getUnreachableStates( const automaton::DFA & fsm ) {
// 1a
std::deque<std::set<automaton::State>> Qi;
Qi.push_back( std::set<automaton::State>( ) );
Qi.at( 0 ). insert( fsm.getInitialState( ) );
int i = 1;
// 1bc
while( true ) {
Qi.push_back( Qi.at( i - 1 ) );
for( const auto & p : Qi.at( i - 1 ) )
for( const auto & transition : fsm.getTransitionsFromState( p ) )
Qi.at( i ).insert( transition.second );
if( Qi.at( i ) == Qi.at( i - 1 ) )
break;
i = i + 1;
}
return Qi.at( i );
}
}