Newer
Older
/*
* 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>
#include <set>
#include <map>
#include <queue>
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
131
132
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 );
}
std::set<automaton::State> AutomatonPropertiesFSM::epsilonClosure( automaton::EpsilonNFA const& fsm, automaton::State const& q ) {
std::set<automaton::State> closure;
std::queue<automaton::State> queue;
std::map<automaton::State, bool> visited;
for( const auto & p : fsm.getStates( ) )
visited[ p ] = false;
queue.push( q );
while( ! queue.empty( ) )
{
const automaton::State & p = queue.front( );
queue.pop( );
visited[ p ] = true;
closure.insert( p );
for( const auto & transition : fsm.getEpsilonTransitionsFromState( p ) )
for (const auto & to : transition.second )
if( visited [ to ] == false )
queue.push( to );
}
return closure;
}