def can_derive(goal_rule,
               rules,
               derived_rules=None,
               max_iter=15,
               verbose=False):
  """Return True if `goal_rule` can be derived given `rules`.

  We perform a relatively naive breadth first search (BFS), with early pruning
  in cases where it can be quickly determined that an intermediate result
  cannot be used in a derivation of our goal.

  Args:
    goal_rule: A QCFGRule representing a string pair to derive.
    rules: A set of QCFGRules.
    derived_rules: If not None, will add any derived QCFGRules that can
      potentially derive `goal_rule` given some substitution to this set.
    max_iter: Maximum number of iterations (i.e. derivation depth) for
      attempting to derive `goal_rule`.
    verbose: Print debugging logging if True.

  Returns:
    True if `goal_rule` can be derived given `rules`.
  """
  # Filter rules to the set that can potentially be used in a derivation
  # of `goal_rule`.
  filtered_rules = _filter_rules(rules, goal_rule)
  if verbose:
    print("filtered_rules: %s" % filtered_rules)
  # Track seen rules.
  seen_rules = set(filtered_rules)
  # Set of derived rules with derivation depth equal to iteration.
  search_state = set(filtered_rules)
  for _ in range(max_iter):
    if not search_state:
      if verbose:
        print("Cannot derive %s." % str(goal_rule))
      return False
    if verbose:
      print("Starting next iteration with search_state:")
      for rule in search_state:
        print(rule)
    new_search_state = set()
    for rule_a in search_state:
      # Attempt to apply every relevant rule to every rule in search_state.
      for rule_b in filtered_rules:
        new_rules = _apply(rule_a, rule_b)
        if verbose:
          print("Applying %s to %s yields %s" % (rule_b, rule_a, new_rules))

        for new_rule in new_rules:
          # Check that application has not led to a malformed rule.
          _verify_arity(new_rule)
          if new_rule in seen_rules:
            continue
          seen_rules.add(new_rule)
          if goal_rule == new_rule:
            if verbose:
              print("Derived %s." % str(goal_rule))
            return True
          # If the generated rule can be potentially used in a derivation of
          # our goal, then add to the search state for the next iteration.
          if _can_maybe_derive_from(new_rule, goal_rule):
            if derived_rules is not None:
              derived_rules.add(new_rule)
            new_search_state.add(new_rule)
          else:
            if verbose:
              print("Cannot derive goal from: %s" % str(new_rule))
    search_state = new_search_state
  # For the datasets we have studied, this limit should not generally apply.
  print("Reached max iterations for rule `%s` given rules `%s`" %
        (goal_rule, filtered_rules))
  return False
Return True if `goal_rule` can be derived given `rules`.

  We perform a relatively naive breadth first search (BFS), with early pruning
  in cases where it can be quickly determined that an intermediate result
  cannot be used in a derivation of our goal.

  Args:
    goal_rule: A QCFGRule representing a string pair to derive.
    rules: A set of QCFGRules.
    derived_rules: If not None, will add any derived QCFGRules that can
      potentially derive `goal_rule` given some substitution to this set.
    max_iter: Maximum number of iterations (i.e. derivation depth) for
      attempting to derive `goal_rule`.
    verbose: Print debugging logging if True.

  Returns:
    True if `goal_rule` can be derived given `rules`.
  
language/compgen/nqg/model/induction/derivation_utils.py