Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
MinimizeVerbose.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <automaton/FSM/DFA.h>
27#include <automaton/TA/DFTA.h>
28
29#include <alib/map>
30#include <alib/set>
31
32#include <global/GlobalData.h>
33
34namespace automaton {
35
36namespace simplify {
37
47public:
58 template < class SymbolType, class StateType >
60
61private:
62 template < class SymbolType, class StateType >
63 static ext::map < std::pair < StateType, StateType >, ext::map < SymbolType, StateType > > print_progress ( const ext::map<std::pair<StateType, ext::set<std::pair<SymbolType, StateType> > >, ext::set<StateType> >& minimizedTransitionFunction);
64};
65
66template < class SymbolType, class StateType >
69
71
72 for(const StateType& state : dfa.getStates())
74
75 for(const std::pair<const ext::pair<StateType, SymbolType>, StateType>& transition : dfa.getTransitions())
76 refactor[transition.first.first].insert(std::make_pair(transition.first.second, transition.second));
77
78 ext::map<StateType, StateType> toEquivalentStates; //original state to equivalent state
79 ext::map<std::pair<StateType, ext::set<std::pair<SymbolType, StateType> > >, ext::set<StateType> > minimizedTransitionFunction; //mapped to the original state
80
81 const StateType *firstFinal = nullptr;
82 const StateType *firstNonfinal = nullptr;
83 for(const StateType& state : dfa.getStates()) {
84 if(dfa.getFinalStates().count(state) == 0) { // not a final state
85 if(!firstNonfinal)
86 firstNonfinal = &state;
87 toEquivalentStates.insert(std::pair<StateType, StateType>(state, *firstNonfinal));
88 } else {
89 if(!firstFinal)
90 firstFinal = &state;
91 toEquivalentStates.insert(std::pair<StateType, StateType>(state, *firstFinal));
92 }
93 }
94
95 unsigned prevSize = 0;
96 while ( true ) {
97 for(const std::pair<const StateType, ext::map<SymbolType, StateType> >& transition : refactor) {
98 const StateType& from = toEquivalentStates.find(transition.first)->second;
100
101 for(const std::pair<const SymbolType, StateType> & transitionFromState : transition.second)
102 transitionFunction.insert(std::make_pair(transitionFromState.first, toEquivalentStates.find(transitionFromState.second)->second));
103
104 minimizedTransitionFunction[std::make_pair(from, transitionFunction)].insert(transition.first);
105 }
106
107 res.push_back ( print_progress ( minimizedTransitionFunction) );
108
109 if (minimizedTransitionFunction.size() == prevSize)
110 break;
111
112 prevSize = minimizedTransitionFunction.size();
113 toEquivalentStates.clear();
114
115 for(const std::pair<const std::pair<StateType, ext::set<std::pair<SymbolType, StateType> > >, ext::set<StateType> >& transition : minimizedTransitionFunction)
116 for(const StateType& target : transition.second)
117 toEquivalentStates.insert(std::make_pair(target, *(transition.second.begin())));
118
119 minimizedTransitionFunction.clear();
120 }
121
122 return res;
123}
124
125#define RESETSS(x) {(x).clear(); (x).str("");}
126
127template < class SymbolType, class StateType >
128ext::map<std::pair<StateType, StateType>, ext::map<SymbolType, StateType>> MinimizeVerbose::print_progress ( const ext::map<std::pair<StateType, ext::set<std::pair<SymbolType, StateType> > >, ext::set<StateType> >& minimizedTransitionFunction) {
129 /* need to restruct this first so we have table like: orig state | new state | trans_symb_1 | trans_symb_2 | ... | trans_symb_n */
130 // we surely have DFA here (transition map hence)
132 for(const auto& kv: minimizedTransitionFunction) {
133 for(const auto& state : kv.second) {
135 for(const auto& transition : kv.first.second) {
136 stateTransMap.insert(std::make_pair(transition.first, transition.second));
137 }
138 printMap.insert(std::make_pair(std::make_pair(state, kv.first.first), stateTransMap));
139 }
140 }
141 return printMap;
142}
143
144} /* namespace simplify */
145
146} /* namespace automaton */
147
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
const ext::set< StateType > & getFinalStates() const &
Definition: DFA.h:183
const ext::map< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: DFA.h:473
const ext::set< StateType > & getStates() const &
Definition: DFA.h:134
Definition: MinimizeVerbose.h:46
static ext::vector< ext::map< std::pair< StateType, StateType >, ext::map< SymbolType, StateType > > > minimize(const automaton::DFA< SymbolType, StateType > &dfa)
Definition: MinimizeVerbose.h:67
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
return res
Definition: MinimizeByPartitioning.h:145
Definition: ToGrammar.h:31
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79