dfa.py 文件源码

def longest_string(self):  # type: () -> String
        """
        Returns an example of a maximally long string recognized by this DFA.

        If the language is infinite, raises InfiniteLanguageError.
        If the language is empty, raises EmptyLanguageError.

        The algorithm is similar to the one described in these lecture notes
        for deciding whether a language is finite:
        http://math.uaa.alaska.edu/~afkjm/cs351/handouts/non-regular.pdf
        """

        # Compute what we're calling the "acceptable subgraph" by restricting to
        # states which are (1) descendants of a start state, and (2) ancestors of
        # an accepting state. These two properties imply that there is at least
        # one walk between these two states, corresponding to a string present in
        # the language.
        acceptable_subgraph = self._acceptable_subgraph
        if len(acceptable_subgraph.node) == 0:
            # If this graph is _empty_, then the language is empty.
            raise EmptyLanguageError()

        # Otherwise, we try to find the longest path in it. Internally, networkx
        # does this by topologically sorting the graph (which only works if it's
        # a DAG), then using the sorted graph to construct the longest path in
        # linear time.
        try:
            longest_path = nx.algorithms.dag.dag_longest_path(
                acceptable_subgraph)
        except nx.NetworkXUnfeasible:
            # If a topological sort is not possible, this means there is a
            # cycle, and the recognized language is infinite. In this case,
            # nx raises ``nx.NetworkXUnfeasible``.
            raise InfiniteLanguageError()

        # To show that the longest path must originate at the start node,
        # consider 3 cases for the position of s in a longest path P from u to v:
        #
        # (a) At the beginning. Done; this is what we were seeking to prove.
        # (b) On the path, but not at the beginning. In this case, u is
        #     reachable from s (by property (1) above), and s in reachable from
        #     u (since s is on a path from u to v). This means the graph
        #     contains a cycle, which contradicts that we've constructed a
        #     topological sort on it.
        # (c) Disjoint from s. Let P' be a path connecting s to u (which must
        #     exist by property (1)). If this path contains a vertex u'!=u in P,
        #     then P ? P' contains a cycle (from u to u' on P and from u' to u
        #     on P'), which is a contradiction. But then P ? P' is a path, which
        #     contains at least one more vertex than P (in particular, s), and
        #     so is a longer path, which contradicts the maximality assumption.

        chars = []
        for state1, state2 in zip(longest_path, longest_path[1:]):
            edges = self.succ[state1][state2]
            chars.append(next(six.itervalues(edges))['transition'])
        return type(self.alphabet[0])().join(chars)