nfa.py 文件源码

python
阅读 30 收藏 0 点赞 0 评论 0

项目:simone 作者: matheuspb 项目源码 文件源码
def merge_equivalent(self) -> None:
        """ Merges equivalent states """
        if not self.is_deterministic():
            raise RuntimeError("Automata is non-deterministic")

        # pairs of undistinguishable states
        undistinguishable = set()  # type: Set[FrozenSet[str]]

        # initially, you can't distinguish final and non-final states
        for pair in combinations(self._states - self._final_states, 2):
            undistinguishable.add(frozenset(pair))
        for pair in combinations(self._final_states, 2):
            undistinguishable.add(frozenset(pair))

        # find new distinguishable states
        while True:
            new_distinguishable_found = False
            undistinguishable_copy = undistinguishable.copy()
            for state_a, state_b in undistinguishable_copy:
                if not self._are_undistinguishable(
                        state_a, state_b, undistinguishable_copy):
                    undistinguishable.remove(frozenset((state_a, state_b)))
                    new_distinguishable_found = True
            if not new_distinguishable_found:
                break

        for state_a, state_b in undistinguishable:
            self._merge_states(state_a, state_b)
评论列表
文章目录


问题


面经


文章

微信
公众号

扫码关注公众号