Awali
Another Weighted Automata library
n_ultimate.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_N_ULTIMATE_HH
18 # define AWALI_ALGOS_N_ULTIMATE_HH
19 
20 # include <iterator> // std::distance
21 # include <stdexcept>
22 
26 #include <awali/sttc/misc/raise.hh>
27 
28 namespace awali { namespace sttc {
29 
49  template <typename Context>
50  mutable_automaton<Context>
51  n_ultimate(const Context& ctx, typename Context::labelset_t::value_t a, unsigned n)
52  {
53  const auto& gens = ctx.labelset()->genset();
54  size_t sz = std::distance(std::begin(gens), std::end(gens));
55  require(2 <= sz, "n_ultimate: the alphabet needs at least 2 letters");
56  require(n > 0, "n_ultimate: automaton defined for n>0");
57  require(gens.has(a),"n_ultimate: ", "letter not in alphabet");
58  using context_t = Context;
59  using automaton_t = mutable_automaton<context_t>;
60  automaton_t res = make_shared_ptr<automaton_t>(ctx);
61 
62  auto init = res->add_state();
63  res->set_initial(init);
64  for (auto l: gens)
65  res->new_transition(init, init, l);
66 
67  auto prev = res->add_state();
68  res->new_transition(init, prev, a);
69 
70  while (--n)
71  {
72  auto next = res->add_state();
73  for (auto l: gens)
74  res->new_transition(prev, next, l);
75  prev = next;
76  }
77  res->set_final(prev);
78  return res;
79  }
80 
81 }}//end of ns awali::stc
82 
83 #endif // !AWALI_ALGOS_N_ULTIMATE_HH
The semiring of Natural numbers.
Definition: n.hh:34
mutable_automaton< Context > n_ultimate(const Context &ctx, typename Context::labelset_t::value_t a, unsigned n)
Returns an automaton which recognizes words with a specific n-ultimate letter.
Definition: n_ultimate.hh:51
std::shared_ptr< internal::mutable_automaton_impl< Context > > mutable_automaton
Definition: mutable_automaton.hh:45
void require(bool b, Args &&... args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:55
Main namespace of Awali.
Definition: ato.hh:22