Awali
Another Weighted Automata library
standard.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_ALGOS_STANDARD_HH
18 # define AWALI_ALGOS_STANDARD_HH
19 
20 # include <set>
21 
22 #include <awali/sttc/algos/copy.hh>
25 #include <awali/sttc/ctx/fwd.hh>
26 #include <awali/sttc/ctx/traits.hh>
28 #include <awali/sttc/misc/raise.hh>
29 #include <awali/sttc/misc/set.hh>
30 
31 namespace awali { namespace sttc {
32 
33 
34  /*-------------------------.
35  | is_standard(automaton). |
36  `-------------------------*/
37 
38  template <typename Aut>
39  bool
40  is_standard(const Aut& a)
41  {
42  return
43  a->num_initials() == 1
44  && a->weightset()->is_one(a->weight_of(*(a->initial_transitions().begin())))
45  // No arrival on the initial state.
46  && a->in(a->dst_of(*(a->initial_transitions().begin()))).empty();
47  }
48 
49  /*----------------------.
50  | standard(automaton). |
51  `----------------------*/
52 
56  template <typename Aut>
57  void
58  standard_here(Aut& aut)
59  {
60  if (is_standard(aut))
61  return;
62  const auto& ws = *aut->weightset();
63  const auto& inits = aut->initial_transitions();
64  std::vector<transition_t> initials{begin(inits), end(inits)};
65 
66  // See TAF-Kit documentation for the implementation details.
67  //
68  // (i.a) Add a new state s...
69  auto ini = aut->add_state();
70  for (auto ti: initials)
71  {
72  // The initial state.
73  auto i = aut->dst_of(ti);
74  auto wi = aut->weight_of(ti);
75  for (auto t: aut->all_out(i))
76  aut->add_transition(ini, aut->dst_of(t), aut->label_of(t),
77  ws.mul(wi, aut->weight_of(t)));
78  aut->del_transition(ti);
79 
80  // (iv) Remove the former initial states of A that are the
81  // destination of no incoming transition.
82  if (aut->all_in(i).empty())
83  aut->del_state(i);
84  }
85  // (i.b) Make [state s] initial, with initial multiplicity equal
86  // to the unit of the multiplicity semiring.
87  aut->set_initial(ini);
88  }
89 
90  template <typename Aut>
91  Aut
92  standard(Aut& aut, bool keep_history=true) {
93  auto out = copy(aut, keep_history);
94  standard_here(out);
95  return out;
96  }
97 
98  /*-------------------.
99  | standard(ratexp). |
100  `-------------------*/
101 
102  namespace rat
103  {
108  template <typename Aut,
109  typename Context = context_t_of<Aut>>
111  : public Context::const_visitor
112  {
113  public:
114  using automaton_t = Aut;
115  using context_t = Context;
118 
119  using super_type = typename Context::const_visitor;
120 
121  constexpr static const char* me() { return "standard"; }
122 
124  : ws_(*ctx.weightset())
125  , res_(make_shared_ptr<automaton_t>(ctx))
126  {}
127 
129  operator()(const typename context_t::ratexp_t& v)
130  {
131  v->accept(*this);
132  res_->set_initial(initial_);
133  return std::move(res_);
134  }
135 
141 
143  {
144  initial_ = res_->add_state();
145  }
146 
148  {
149  auto i = res_->add_state();
150  initial_ = i;
151  res_->set_final(i);
152  }
153 
155  {
156  auto i = res_->add_state();
157  auto f = res_->add_state();
158  initial_ = i;
159  res_->new_transition(i, f, e.value());
160  res_->set_final(f);
161  }
162 
164  using states_t = std::set<state_t>;
165  states_t
167  {
168  states_t res;
169  for (auto t: res_->final_transitions())
170  res.insert(res_->src_of(t));
171  return res;
172  }
173 
175  {
176  states_t other_finals = finals();
177  e.head()->accept(*this);
178  state_t initial = initial_;
179  for (auto c: e.tail())
180  {
181  c->accept(*this);
182  for (auto t: res_->all_out(initial_))
183  // Not set_transition: for instance 'a*+a*' will make
184  // "initial" go twice to post().
185  res_->add_transition(initial,
186  res_->dst_of(t),
187  res_->label_of(t),
188  res_->weight_of(t));
189  res_->del_state(initial_);
190  }
191  initial_ = initial;
192  }
193 
195  {
196  // The set of the final states that were introduced in pending
197  // parts of the automaton (for instance if we are in the rhs
198  // of "a+bc", recording the final state for "a").
199  states_t other_finals = finals();
200 
201  // Traverse the first part of the product, handle left_weight.
202  e.head()->accept(*this);
203  state_t initial = initial_;
204 
205  // Then the remainder.
206  for (auto c: e.tail())
207  {
208  // The set of the current (left-hand side) final transitions.
209  auto ftr_ = res_->final_transitions();
210  // Store transitions by copy.
211  using transs_t = std::vector<transition_t>;
212  transs_t ftr{ begin(ftr_), end(ftr_) };
213 
214  // Visit the next member of the product.
215  c->accept(*this);
216  // Branch all the previously added final transitions to
217  // the successors of the new initial state.
218  for (auto t1: ftr)
219  if (!sttc::internal::has(other_finals, res_->src_of(t1)))
220  {
221  // Remove the previous final transition first, as we
222  // might add a final transition for the same state
223  // later.
224  //
225  // For instance on "{2}a+({3}\e+{5}a)", the final
226  // state s1 of {2}a will be made final thanks to
227  // {3}\e. So if we compute the new transitions from
228  // s1 and then remove t1, we will have removed the
229  // fact that s1 is final thanks to {3}\e.
230  //
231  // Besides, s1 will become final with weight {3}, which
232  // might interfere with {5}a too.
233  auto s1 = res_->src_of(t1);
234  auto w1 = res_->weight_of(t1);
235  res_->del_transition(t1);
236  for (auto t2: res_->all_out(initial_))
237  res_->set_transition(s1,
238  res_->dst_of(t2),
239  res_->label_of(t2),
240  ws_.mul(w1, res_->weight_of(t2)));
241  }
242  res_->del_state(initial_);
243  }
244  initial_ = initial;
245  }
246 
247  // See star_here().
249  {
250  states_t other_finals = finals();
251  e.sub()->accept(*this);
252  // The "final weight of the initial state", starred.
253  weight_t w = ws_.star(res_->get_final_weight(initial_));
254  // Branch all the final states (but initial) to the successors
255  // of initial.
256  for (auto ti: res_->out(initial_))
257  {
258  res_->lmul_weight(ti, w);
259  for (auto tf: res_->final_transitions())
260  if (res_->src_of(tf) != initial_
261  && !sttc::internal::has(other_finals, res_->src_of(tf)))
262  // Note that the weight of ti has already been
263  // multiplied, on the left, by w.
264  //
265  // Not set_transition, as for instance with "a**", the
266  // second star modifies many existing transitions.
267  res_->add_transition
268  (res_->src_of(tf),
269  res_->dst_of(ti),
270  res_->label_of(ti),
271  ws_.mul(res_->weight_of(tf), res_->weight_of(ti)));
272  }
273  for (auto tf: res_->final_transitions())
274  if (!sttc::internal::has(other_finals, res_->src_of(tf)))
275  res_->rmul_weight(tf, w);
276  res_->set_final(initial_, w);
277  }
278 
280  {
281  e.sub()->accept(*this);
282  for (auto t: res_->all_out(initial_))
283  res_->lmul_weight(t, e.weight());
284  }
285 
287  {
288  states_t other_finals = finals();
289  e.sub()->accept(*this);
290  for (auto t: res_->final_transitions())
291  if (! sttc::internal::has(other_finals, res_->src_of(t)))
292  res_->rmul_weight(t, e.weight());
293  }
294 
295  private:
296  const weightset_t& ws_;
297  automaton_t res_;
298  state_t initial_ = automaton_t::element_type::null_state();
299  };
300 
301  } // rat::
302 
303  /* @brief Convert a ratexp to a standard automaton.
304  *
305  * @tparam Aut static type of the generated automaton
306  * @tparam Context static type of the context of the generated automaton
307  * @param ctx the context of the generated automaton
308  * @param exp the rational expression
309  * @return the standard automaton
310  */
311  template <typename Aut,
312  typename Context = context_t_of<Aut>>
313  Aut
314  standard(const Context& ctx, const typename Context::ratexp_t& e)
315  {
317  return standard(e);
318  }
319 
320  /* @brief Convert a ratexp to a standard automaton.
321  *
322  * @tparam RatExpSet type of the context of the rational expression
323  * @param rs the context of the rational expression
324  * @param exp the rational expression
325  * @return the standard automaton
326  */
327  template <typename RatExpSet>
328  inline
329  mutable_automaton<typename RatExpSet::context_t>
330  standard(const RatExpSet& rs, const typename RatExpSet::ratexp_t& e)
331  {
332  rat::standard_visitor<mutable_automaton<typename RatExpSet::context_t>, typename RatExpSet::context_t> standard{rs.context()};
333  return standard(e);
334  }
335 
336 
337  }}//end of ns awali::stc
338 
339 #endif // !AWALI_ALGOS_STANDARD_HH
The semiring of complex numbers.
Definition: c.hh:44
Definition: ratexp.hh:280
Definition: ratexp.hh:262
Convert a ratexp to a standard automaton.
Definition: standard.hh:112
weight_t_of< context_t > weight_t
Definition: standard.hh:117
constexpr static const char * me()
Definition: standard.hh:121
AWALI_RAT_VISIT(atom, e)
Definition: standard.hh:154
AWALI_RAT_VISIT(one,)
Definition: standard.hh:147
AWALI_RAT_VISIT(rweight, e)
Definition: standard.hh:286
AWALI_RAT_VISIT(star, e)
Definition: standard.hh:248
standard_visitor(const context_t &ctx)
Definition: standard.hh:123
AWALI_RAT_VISIT(sum, e)
Definition: standard.hh:174
Context context_t
Definition: standard.hh:115
typename Context::const_visitor super_type
Definition: standard.hh:119
AWALI_RAT_VISIT(lweight, e)
Definition: standard.hh:279
automaton_t operator()(const typename context_t::ratexp_t &v)
Definition: standard.hh:129
weightset_t_of< context_t > weightset_t
Definition: standard.hh:116
AWALI_RAT_VISIT(zero,)
Definition: standard.hh:142
states_t finals()
Definition: standard.hh:166
AWALI_RAT_VISIT(prod, e)
Definition: standard.hh:194
std::set< state_t > states_t
The current set of final states.
Definition: standard.hh:164
Aut automaton_t
Definition: standard.hh:114
Definition: ratexp.hh:176
An inner node with multiple children.
Definition: ratexp.hh:115
An inner node implementing a weight.
Definition: ratexp.hh:208
weightset_description weightset(const std::string &k)
bool has(const std::map< Key, Value, Compare, Alloc > &s, const Key &e)
Definition: map.hh:53
bool is_standard(const Aut &a)
Definition: standard.hh:40
SharedPtr make_shared_ptr(Args &&... args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:29
typename internal::weight_t_of_impl< internal::base_t< ValueSet > >::type weight_t_of
Helper to retrieve the type of the weights of a value set.
Definition: traits.hh:81
Aut standard(Aut &aut, bool keep_history=true)
Definition: standard.hh:92
AutOut copy(const AutIn &input, Pred keep_state, bool keep_history=true, bool transpose=false)
A copy of input keeping only its states that are accepted by keep_state.
Definition: copy.hh:189
void standard_here(Aut &aut)
Turn aut into a standard automaton.
Definition: standard.hh:58
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
#define AWALI_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:73