Vcsn  2.2
Be Rational
is-deterministic.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <queue>
4 #include <unordered_set>
5 
7 #include <vcsn/ctx/traits.hh>
8 #include <vcsn/dyn/automaton.hh>
9 
10 namespace vcsn
11 {
12 
14  template <Automaton Aut>
15  inline bool
16  is_deterministic(const Aut& aut, state_t_of<Aut> s)
17  {
18  using automaton_t = Aut;
20  "is_deterministic: requires free labelset");
21 
22  using label_t = label_t_of<automaton_t>;
23  std::unordered_set<label_t> seen;
24  for (auto t : all_out(aut, s))
25  if (!seen.insert(aut->label_of(t)).second)
26  return false;
27  return true;
28  }
29 
31  template <Automaton Aut>
32  inline size_t
33  num_deterministic_states(const Aut& aut)
34  {
35  static_assert(labelset_t_of<Aut>::is_free(),
36  "num_deterministic_states: requires free labelset");
37 
38  size_t res = 0;
39  for (auto s: aut->states())
40  res += is_deterministic(aut, s);
41  return res;
42  }
43 
45  template <Automaton Aut>
46  inline size_t
48  {
50  }
51 
54  template <Automaton Aut>
55  inline bool
56  is_deterministic(const Aut& aut)
57  {
58  static_assert(labelset_t_of<Aut>::is_free(),
59  "is_deterministic: requires free labelset");
60 
61  if (1 < initial_transitions(aut).size())
62  return false;
63 
64  for (auto s: aut->states())
65  if (!is_deterministic(aut, s))
66  return false;
67  return true;
68  }
69 
71  template <Automaton Aut>
72  inline bool
73  is_codeterministic(const Aut& aut)
74  {
75  return is_deterministic(transpose(aut));
76  }
77 
78  namespace dyn
79  {
80  namespace detail
81  {
83  template <Automaton Aut>
84  bool
86  {
87  return is_deterministic(aut->as<Aut>());
88  }
89 
91  template <Automaton Aut>
92  bool
94  {
95  return is_codeterministic(aut->as<Aut>());
96  }
97  }
98  }
99 } // namespace vscn
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
bool is_codeterministic(const automaton &aut)
Bridge.
bool is_deterministic(const automaton &aut)
Bridge.
Definition: a-star.hh:8
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:227
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:137
size_t num_codeterministic_states(const Aut &aut)
Number of non-deterministic states of transpositive automaton.
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
size_t num_deterministic_states(const Aut &aut)
Number of non-deterministic states.
bool is_codeterministic(const Aut &aut)
Whether the transpositive automaton is deterministic.
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)