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
/*
* NFADeterminizer.cpp
*
* Created on: 16. 1. 2014
* Author: Jan Vesely
*/
#include "common/NFACommon.h"
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <deque>
#include <algorithm>
#include <container/ObjectsSet.h>
namespace automaton {
namespace determinize {
template < class SymbolType, class StateType >
automaton::DFA < SymbolType, std::set < StateType > > Determinize::determinize ( const automaton::MultiInitialStateNFA < SymbolType, StateType > & nfa ) {
// 1, 4
std::set < StateType > initialState = nfa.getInitialStates ( );
automaton::DFA < SymbolType, std::set < StateType > > res ( initialState );
res.setInputAlphabet ( nfa.getInputAlphabet ( ) );
// 2
std::deque < std::set < StateType > > todo;
todo.push_back ( std::move ( initialState ) );
do {
// 3a, c
std::set < StateType > state = std::move ( todo.front ( ) );
todo.pop_front ( );
// 3b
for ( const SymbolType & input : nfa.getInputAlphabet ( ) ) {
std::set < StateType > dfaState;
for ( StateType nfaState : state ) {
auto iter = nfa.getTransitions ( ).find ( std::make_pair ( std::move ( nfaState ), input ) );
if ( iter != nfa.getTransitions ( ).end ( ) )
dfaState.insert ( iter->second.begin ( ), iter->second.end ( ) );
}
// 4
bool existed = !res.addState ( dfaState );
if ( !existed ) todo.push_back ( dfaState );
// 3b
res.addTransition ( state, input, std::move ( dfaState ) );
}
} while ( !todo.empty ( ) );
// 5
const std::set < StateType > & finalLabels = nfa.getFinalStates();
for ( const std::set < StateType > & dfaState : res.getStates ( ) )
if ( ! ext::excludes ( finalLabels.begin ( ), finalLabels.end ( ), dfaState.begin ( ), dfaState.end ( ) ) )
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
res.addFinalState ( dfaState );
return res;
}
template < class SymbolType, class StateType >
automaton::DFA < SymbolType, std::set < StateType > > Determinize::determinize ( const automaton::NFA < SymbolType, StateType > & nfa ) {
// 1, 4
std::set < StateType > initialState;
initialState.insert ( nfa.getInitialState ( ) );
automaton::DFA < SymbolType, std::set < StateType > > res ( initialState );
res.setInputAlphabet ( nfa.getInputAlphabet ( ) );
// 2
std::deque < std::set < StateType > > todo;
todo.push_back ( std::move ( initialState ) );
do {
// 3a, c
std::set < StateType > state = std::move ( todo.front ( ) );
todo.pop_front ( );
// 3b
for ( const SymbolType & input : nfa.getInputAlphabet ( ) ) {
std::set < StateType > dfaState;
for ( StateType nfaState : state ) {
auto iter = nfa.getTransitions ( ).find ( std::make_pair ( std::move ( nfaState ), input ) );
if ( iter != nfa.getTransitions ( ).end ( ) )
dfaState.insert ( iter->second.begin ( ), iter->second.end ( ) );
}
// 4
bool existed = !res.addState ( dfaState );
if ( !existed ) todo.push_back ( dfaState );
// 3b
res.addTransition ( state, input, std::move ( dfaState ) );
}
} while ( !todo.empty ( ) );
// 5
const std::set < StateType > & finalLabels = nfa.getFinalStates();
for ( const std::set < StateType > & dfaState : res.getStates ( ) )
if ( ! ext::excludes ( finalLabels.begin ( ), finalLabels.end ( ), dfaState.begin ( ), dfaState.end ( ) ) )
res.addFinalState ( dfaState );
return res;
}
} /* namespace determinize */
} /* namespace automaton */