我将如何确定每个状态是否具有唯一的输入/输出序列？有没有标准化的技术或方法？我似乎无法在网上找到任何东西。
谢谢你的帮助！
问问题
978 次
1 回答
1
对于确定性 FSM（即没有 epsilon 状态转换的 FSM），当且仅当满足以下条件时，才会有一个唯一的输入序列导致该状态：
1）必须存在通往状态的路径。（孤立的不可达状态不符合条件）。
2) 没有返回起始状态的路径（否则，直接行军到目标状态会到达它，并且循环回到起始状态然后进行直接行军的行军也可以）。
3) 对于每个状态 S，要么目标状态不可从 S 到达，要么 S是目标状态，要么从起始状态到 S 存在唯一路径，并且从 S 到目标状态存在唯一路径。
假设您使用的是有向图对象表示，这将意味着图中没有终止于起始状态的边，并且对于图中的每个状态 S，也没有从 S 到目标的路径，或者有一个独特的。
如果您试图在代码中找出这个问题，您可以使用修改后的 Dijkstra 算法来解决这个问题。
请注意，这仅针对具有唯一输入序列的地址。拥有唯一的输出序列需要更加小心，因为实际上可能有多个输入序列产生相同的输出序列。不过思路是一样的，只是必须修改第三个条件：
3）对于每一个状态S，要么目标状态不能从S到达，要么S是目标状态，或者如果S和T都有到目标状态的路径，它们必须生成相同的输出序列，并且输出序列从起始状态到 S 生成的输出序列和从起始状态到 T 生成的输出序列必须相同。
同样，修改后的 Dijkstra 可能是最好的选择。
于 2014-12-30T21:59:40.140 回答