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: Returns True if any strings can be accepted
  when starting from ``state``.
docstr_tok: ["Returns","True","if","any","strings","can","be","accepted","when","starting","from","``","state","``","."]
code: def is_live(self, state):
      """Returns True if any strings can be accepted
      when starting from ``state``."""
      if self.is_accepting(state):
          return True
  
      # We work this out by calculating is_live for all nodes
      # reachable from state which have not already had it calculated.
      cache = self.__cache("is_live")
      try:
          return cache[state]
      except KeyError:
          pass
  
      # roots are states that we know already must be live,
      # either because we have previously calculated them to
      # be or because they are an accepting state.
      roots = set()
  
      # We maintain a backwards graph where ``j in backwards_graph[k]``
      # if there is a transition from j to k. Thus if a key in this
      # graph is live, so must all its values be.
      backwards_graph = defaultdict(set)
  
      # First we find all reachable nodes from i which have not
      # already been cached, noting any which are roots and
      # populating the backwards graph.
  
      explored = set()
      queue = deque([state])
      while queue:
          j = queue.popleft()
          if cache.get(j, self.is_accepting(j)):
              # If j can be immediately determined to be live
              # then there is no point in exploring beneath it,
              # because any effect of states below it is screened
              # off by the known answer for j.
              roots.add(j)
              continue
  
          if j in cache:
              # Likewise if j is known to be dead then there is
              # no point exploring beneath it because we know
              # that all nodes reachable from it must be dead.
              continue
  
          if j in explored:
              continue
          explored.add(j)
  
          for k in self.successor_states(j):
              backwards_graph[k].add(j)
              queue.append(k)
  
      marked_live = set()
      queue = deque(roots)
      while queue:
          j = queue.popleft()
          if j in marked_live:
              continue
          marked_live.add(j)
          for k in backwards_graph[j]:
              queue.append(k)
      for j in explored:
          cache[j] = j in marked_live
  
      return cache[state]
  
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 16 for calling the DFA obj's underlying member method code with example usage: obj.is_live(state) and returns: cache, True, cache