验证FSM中从“开始”状态到“结束”状态的每个状态的可达性

Question

我从一个有N个状态的有限状态机开始（即状态图上的N个顶点）。 其中一个状态是“开始”状态，一个状态是“结束”状态。在

我想做的是-

1. 检查是否可以从“开始”状态访问其他N-2状态
2. 检查是否可以从N-2个状态中的每个状态到达“结束”状态

实现这一目标的最佳算法是什么？
另外，是否有任何Python模块可以以最小的工作量完成这个验证（比如仅仅是一个函数调用）？在

Answer 1

我找到了这个Python模块Networkx，它对我帮助很大。
This(networkx.最短路径)特别是我使用的函数。在

贴在对我有用的溶液下面。在

import networkx as nx

G = nx.DiGraph()
G.add_nodes_from(["Start", "a", "b", "c", "End"])
G.add_edges_from([("Start", "a"), ("Start", "c"), ("a", "b"), ("b", "a"), ("c", "End")])

total_num_nodes = G.number_of_nodes()

if len(nx.shortest_path(G, source="Start")) < total_num_nodes:
    print "\nThis FSM has inaccessible states"
else:
    print "\nAll nodes reachable from 'Start'"

H = G.reverse()
if len(nx.shortest_path(H, source="End")) < total_num_nodes:
    print "\nThis FSM has dead-end states"
else:
    print "\nAll nodes have a path to reach the 'End' state"

Answer 2

如果您正在寻找一个简单的解决方案，您可以使用Floyd-Warshall algorithm计算FSM转换函数的transitive closure。这将给您一个NxN数组，告诉您对于任何两个状态P和{}是否可以从P访问{}。它需要O(N3)，如果N不是太大，这应该可以。在

算法可以用python的五行代码编写。这里trans是一个列表列表，如果存在从s到{}的直接转换，那么{}就是{}，否则{}。（s和{}应该是整数）。它就地修改这个数组；当它返回时，trans[s][t]是True，如果存在从s到{}的路径：

def warshall(trans):
  for k in range(len(trans)):
    for i in range(len(trans)):
      for j in range(len(trans)):
        trans[i][j] = trans[i][j] or trans[i][k] and trans[k][j]

（最后一行可能是用|=编写的，但我认为这不太清楚。）

该算法也可用于计算“所有最短路径”数组，通常被引用为解决该问题的方法。为此，我们从一个转换数组开始，其中trans[i][j]是从i到{}（如果没有直接转换，infinity）的转换成本，并将最后一行替换为：

^{pr2}$

对于一个FSM，您通常会将所有代价设置为1或{}，然后您将得到从s到{}的最短路径长度。在

你会在互联网上找到算法的正式证明（在算法和图论的标准教科书中也有），所以我只做一个大纲：

为了简化类型，我假设节点由0…N-1范围内的整数表示。如果每个p0…pi小于k，我们将称之为路径s→p0→…→pi→ta<k-path。因此，从s到{}的唯一可能的<0-路径是平凡路径s→t，如果它存在于图中，s到{}的每一条路径都是<N-路径。在

现在，如果有一条<k+1-路径从s到{}，那么要么有一条<k-从s到{}，要么有一条<k-从s到{}的路径和另一条{}-从{}到{}的路径。（这只是另一种说法，即每个非单数路径都有一个最大内部节点，并且可以在该节点处划分为两条最大值较小的路径。）

Warshall算法的每次迭代从<k-路径的转移数组开始，通过添加穿过节点k的所有路径组合，以<k-路径的转换数组结束。最后，我们得到了<N-路径的数组，正如我们之前所观察到的，它包含了所有可能的路径。在

Answer 3

您可以使用起始状态中的任何travesal（DFS/BFS/…）并将已访问状态标记为可访问。对于核心可获得性问题，只需反转边并从末尾开始。在