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: Checks whether this DFA and other match precisely the same
  language.
  
  Uses the classic algorithm of Hopcroft and Karp (more or less):
  Hopcroft, John E. A linear algorithm for testing equivalence
  of finite automata. Vol. 114. Defense Technical Information Center, 1971.
docstr_tok: ["Checks","whether","this","DFA","and","other","match","precisely","the","same","language",".","Uses","the","classic","algorithm","of","Hopcroft","and","Karp","(","more","or","less",")",":","Hopcroft",",","John","E.","A","linear","algorithm","for","testing","equivalence","of","finite","automata",".","Vol",".","114",".","Defense","Technical","Information","Center",",","1971","."]
code: def equivalent(self, other):
      """Checks whether this DFA and other match precisely the same
      language.
  
      Uses the classic algorithm of Hopcroft and Karp (more or less):
      Hopcroft, John E. A linear algorithm for testing equivalence
      of finite automata. Vol. 114. Defense Technical Information Center, 1971.
      """
  
      # The basic idea of this algorithm is that we repeatedly
      # merge states that would be equivalent if the two start
      # states were. This starts by merging the two start states,
      # and whenever we merge two states merging all pairs of
      # states that are reachable by following the same character
      # from that point.
      #
      # Whenever we merge two states, we check if one of them
      # is accepting and the other non-accepting. If so, we have
      # obtained a contradiction and have made a bad merge, so
      # the two start states must not have been equivalent in the
      # first place and we return False.
      #
      # If the languages matched are different then some string
      # is contained in one but not the other. By looking at
      # the pairs of states visited by traversing the string in
      # each automaton in parallel, we eventually come to a pair
      # of states that would have to be merged by this algorithm
      # where one is accepting and the other is not. Thus this
      # algorithm always returns False as a result of a bad merge
      # if the two languages are not the same.
      #
      # If we successfully complete all merges without a contradiction
      # we can thus safely return True.
  
      # We maintain a union/find table for tracking merges of states.
      table = {}
  
      def find(s):
          trail = [s]
          while trail[-1] in table and table[trail[-1]] != trail[-1]:
              trail.append(table[trail[-1]])
  
          for t in trail:
              table[t] = trail[-1]
  
          return trail[-1]
  
      def union(s, t):
          s = find(s)
          t = find(t)
          table[s] = t
  
      alphabet = sorted(set(self.alphabet) | set(other.alphabet))
  
      queue = deque([((self.start, other.start))])
      while queue:
          self_state, other_state = queue.popleft()
  
          # We use a DFA/state pair for keys because the same value
          # may represent a different state in each DFA.
          self_key = (self, self_state)
          other_key = (other, other_state)
  
          # We have already merged these, no need to remerge.
          if find(self_key) == find(other_key):
              continue
  
          # We have found a contradiction, therefore the two DFAs must
          # not be equivalent.
          if self.is_accepting(self_state) != other.is_accepting(
              other_state
          ):
              return False
  
          # Merge the two states
          union(self_key, other_key)
  
          # And also queue any logical consequences of merging those
          # two states for merging.
          for c in alphabet:
              queue.append(
                  (
                      self.transition(self_state, c),
                      other.transition(other_state, c),
                  )
              )
      return True
  
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 21 for calling the DFA obj's underlying member method code with example usage: obj.equivalent(other) and returns: True, trail, False