00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifndef AUTOMATA_H
00012 #define AUTOMATA_H
00013
00014 #include <map>
00015 #include <set>
00016 #include <deque>
00017
00018 namespace automata {
00019
00020 template<class STATE, class INPUT, class OUTPUT>
00021 class FA_base {
00022 public:
00023 FA_base(STATE s, OUTPUT d);
00024 FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt);
00025 virtual ~FA_base();
00026
00027 typedef std::map<INPUT, OUTPUT> Transitions;
00028
00029 const std::set<STATE>& states() const;
00030 const std::set<INPUT>& inputs() const;
00031 const Transitions& transitions(STATE s) const;
00032 const STATE start() const;
00033 const OUTPUT deflt() const;
00034 const OUTPUT next(STATE from, INPUT input) const;
00035
00036 void addState(STATE newState);
00037 void addInput(INPUT newInput);
00038 void setTransition(STATE from, INPUT input, OUTPUT to);
00039
00040 protected:
00041 std::set<STATE> states_;
00042 std::set<INPUT> inputs_;
00043 std::map<STATE, Transitions> transitions_;
00044 const Transitions noTransitions;
00045 STATE start_;
00046 OUTPUT default_;
00047 };
00048
00049 template<class STATE, class INPUT, class OUTPUT>
00050 FA_base<STATE, INPUT, OUTPUT>::FA_base(STATE s, OUTPUT d) : states_(), inputs_(), transitions_(), noTransitions(), start_(s), default_(d)
00051 {
00052 states_.insert(s);
00053 }
00054
00055 template<class STATE, class INPUT, class OUTPUT>
00056 FA_base<STATE, INPUT, OUTPUT>::FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt) : states_(states), inputs_(inputs), transitions_(), noTransitions(), start_(start), default_(deflt)
00057 {
00058 if (states_.find(start) == states_.end())
00059 states_.insert(start);
00060 }
00061
00062 template<class STATE, class INPUT, class OUTPUT>
00063 const std::set<STATE>& FA_base<STATE, INPUT, OUTPUT>::states() const
00064 {
00065 return states_;
00066 }
00067
00068 template<class STATE, class INPUT, class OUTPUT>
00069 const std::set<INPUT>& FA_base<STATE, INPUT, OUTPUT>::inputs() const
00070 {
00071 return inputs_;
00072 }
00073
00074 template<class STATE, class INPUT, class OUTPUT>
00075 const STATE FA_base<STATE, INPUT, OUTPUT>::start() const
00076 {
00077 return start_;
00078 }
00079
00080 template<class STATE, class INPUT, class OUTPUT>
00081 const OUTPUT FA_base<STATE, INPUT, OUTPUT>::deflt() const
00082 {
00083 return default_;
00084 }
00085
00086 template<class STATE, class INPUT>
00087 class DFA : public FA_base<STATE, INPUT, STATE> {
00088 public:
00089 DFA(STATE s, STATE deflt): FA_base<STATE, INPUT, STATE>(s, deflt) { }
00090 DFA(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt)
00091 : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
00092 };
00093
00094
00095 template<class STATE, class INPUT>
00096 class NFA : public FA_base<STATE, INPUT, std::set<STATE> > {
00097 public:
00098 NFA(STATE s, std::set<STATE> d): FA_base<STATE, INPUT, std::set<STATE> >(s, d) { }
00099 NFA(std::set<STATE>& states, std::set<INPUT>& inputs, STATE start, std::set<STATE> deflt)
00100 : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
00101
00102 void addTransition(STATE from, INPUT input, STATE to);
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123 template<class NSTATE, class XXX>
00124 DFA<NSTATE,INPUT>* constructDFA( XXX createState )
00125
00126 {
00127 std::map<std::set<STATE>, NSTATE> newStates;
00128
00129 std::set<STATE> startSet;
00130 startSet.insert(FA_base<STATE,INPUT,std::set<STATE> >::start_);
00131 NSTATE nstart = createState(startSet);
00132 newStates[startSet] = nstart;
00133
00134 NSTATE deflt = createState(FA_base<STATE,INPUT,std::set<STATE> >::default_);
00135 newStates[FA_base<STATE,INPUT,std::set<STATE> >::default_] = deflt;
00136
00137 DFA<NSTATE,INPUT>* result = new DFA<NSTATE,INPUT>(nstart, deflt);
00138 result->addState(deflt);
00139
00140 std::deque<std::set<STATE> > todo;
00141 todo.push_back(startSet);
00142
00143 while (todo.size() > 0)
00144 {
00145 const std::set<STATE> from = todo.front();
00146 todo.pop_front();
00147 std::map<INPUT,std::set<STATE> > ntrans;
00148
00149 typename std::set<STATE>::const_iterator s_it;
00150 typename std::map<INPUT, std::set<STATE> >::iterator tr_it;
00151 for (s_it=from.begin(); s_it != from.end(); ++s_it)
00152 {
00153
00154 typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions&
00155 trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[*s_it]);
00156 for (tr_it = trans.begin(); tr_it != trans.end(); ++tr_it)
00157 {
00158 ntrans[tr_it->first].insert(tr_it->second.begin(), tr_it->second.end());
00159 }
00160 }
00161
00162 const NSTATE nfrom = newStates[from];
00163 for (tr_it = ntrans.begin(); tr_it != ntrans.end(); ++tr_it)
00164 {
00165 std::set<STATE> & state(tr_it->second);
00166
00167 NSTATE nstate;
00168 if ( newStates.find(state) == newStates.end() ) {
00169 nstate = createState(state);
00170 result->addState(nstate);
00171 newStates[state] = nstate;
00172
00173 todo.push_back(state);
00174 }
00175 else {
00176 nstate = newStates[state];
00177 }
00178 result->setTransition(nfrom, tr_it->first, nstate);
00179 }
00180 }
00181 const std::set<INPUT>& inp(FA_base<STATE, INPUT, std::set<STATE> >::inputs());
00182 typename std::set<INPUT>::const_iterator i;
00183 for (i=inp.begin(); i != inp.end(); ++i)
00184 result->addInput(*i);
00185 return result;
00186 }
00187 };
00188
00189
00190 template<class STATE, class INPUT, class OUTPUT>
00191 FA_base<STATE,INPUT,OUTPUT>::~FA_base()
00192 {
00193
00194 }
00195
00196 template<class STATE, class INPUT, class OUTPUT>
00197 const typename FA_base<STATE,INPUT,OUTPUT>::Transitions& FA_base<STATE,INPUT,OUTPUT>::transitions(STATE s) const
00198 {
00199 typename std::map<STATE, Transitions>::const_iterator tr = transitions_.find(s);
00200 if (tr != transitions_.end())
00201 return tr->second;
00202 else
00203 return noTransitions;
00204 }
00205
00206 template<class STATE, class INPUT, class OUTPUT>
00207 const OUTPUT FA_base<STATE,INPUT,OUTPUT>::next(STATE from, INPUT input) const
00208 {
00209 const Transitions& tr(transitions(from));
00210 typename Transitions::const_iterator it = tr.find(input);
00211 return it==tr.end() ? default_ : it->second;
00212 }
00213
00214 template<class STATE, class INPUT, class OUTPUT>
00215 void FA_base<STATE,INPUT,OUTPUT>::addState(STATE newState)
00216 {
00217 if (states_.find(newState) == states_.end())
00218 states_.insert(newState);
00219 }
00220
00221
00222 template<class STATE, class INPUT, class OUTPUT>
00223 void FA_base<STATE,INPUT,OUTPUT>::addInput(INPUT newInput)
00224 {
00225 if (inputs_.find(newInput) == inputs_.end())
00226 inputs_.insert(newInput);
00227 }
00228
00229
00230 template<class STATE, class INPUT, class OUTPUT>
00231 void FA_base<STATE,INPUT,OUTPUT>::setTransition(STATE from, INPUT input, OUTPUT to)
00232 {
00233 Transitions& trans(transitions_[from]);
00234 trans[input] = to;
00235 }
00236
00237
00238 template<class STATE, class INPUT>
00239 void NFA<STATE, INPUT>::addTransition(STATE from, INPUT input, STATE to)
00240 {
00241 typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions &
00242 trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[from]);
00243 trans[input].insert(to);
00244 }
00245
00246 }
00247
00248 #endif