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)
评论列表
文章目录