class_docstr: Base class for implementations of deterministic finite
  automata.
  
  This is abstract to allow for the possibility of states
  being calculated lazily as we traverse the DFA (which
  we make heavy use of in our L* implementation - see
  lstar.py for details).
  
  States can be of any hashable type.
class_docstr_tok: ["Base","class","for","implementations","of","deterministic","finite","automata",".","This","is","abstract","to","allow","for","the","possibility","of","states","being","calculated","lazily","as","we","traverse","the","DFA","(","which","we","make","heavy","use","of","in","our","L","*","implementation","-","see","lstar.py","for","details",")",".","States","can","be","of","any","hashable","type","."]
docstr: Return a canonical version of ``self`` as a ConcreteDFA.
  
  The DFA is not minimized, but nodes are sorted and relabelled
  and dead nodes are pruned, so two minimized DFAs for the same
  language will end up with identical canonical representatives.
  This is mildly important because it means that the output of
  L* should produce the same canonical DFA regardless of what
  order we happen to have run it in.
docstr_tok: ["Return","a","canonical","version","of","``","self","``","as","a","ConcreteDFA",".","The","DFA","is","not","minimized",",","but","nodes","are","sorted","and","relabelled","and","dead","nodes","are","pruned",",","so","two","minimized","DFAs","for","the","same","language","will","end","up","with","identical","canonical","representatives",".","This","is","mildly","important","because","it","means","that","the","output","of","L","*","should","produce","the","same","canonical","DFA","regardless","of","what","order","we","happen","to","have","run","it","in","."]
code: def canonicalise(self):
      """Return a canonical version of ``self`` as a ConcreteDFA.
  
      The DFA is not minimized, but nodes are sorted and relabelled
      and dead nodes are pruned, so two minimized DFAs for the same
      language will end up with identical canonical representatives.
      This is mildly important because it means that the output of
      L* should produce the same canonical DFA regardless of what
      order we happen to have run it in.
      """
      # We map all states to their index of appearance in depth
      # first search. This both is useful for canonicalising and
      # also allows for states that aren't integers.
      state_map = {}
      reverse_state_map = []
      accepting = set()
  
      seen = set()
  
      queue = deque([self.start])
      while queue:
          state = queue.popleft()
          if state in state_map:
              continue
          i = len(reverse_state_map)
          if self.is_accepting(state):
              accepting.add(i)
          reverse_state_map.append(state)
          state_map[state] = i
          for _, j in self.transitions(state):
              if j in seen:
                  continue
              seen.add(j)
              queue.append(j)
  
      transitions = [
          {c: state_map[s] for c, s in self.transitions(t)}
          for t in reverse_state_map
      ]
  
      result = ConcreteDFA(transitions, accepting)
      assert self.equivalent(result)
      return result
  
imports: import threading
  from collections import Counter, defaultdict, deque
  from math import inf
  from hypothesis.internal.reflection import proxies
label_desc: Use image node_id 20 for calling the DFA obj's underlying member method code with example usage: obj.canonicalise() and returns: result