“有限状态机”和“状态机”之间有什么区别吗？

Question

我不确定有限状态机和状态机之间是否有区别？我是不是想得太复杂了？

- Carson

---

谢谢你，Prasoon，添加那个标签。 - Carson

Answer 1

我不确定有限状态机和状态机之间是否有区别？我是不是想太多了？

是的，你想得太多了。 :-) 这取决于上下文。

显然，严格解释，“有限状态机”这个术语表示有限数量的状态，而“状态机”则没有这样的承诺。因此，两者是有区别的。

但是，我认为，在谈话的上下文中，人们通常会简单地说“状态机”，而不考虑他们是否指的是“有限状态机”或“状态机”。在我们软件编程领域中，状态机通常以代码形式表示，我们常常可以互换使用“状态机”和“有限状态机”这两个术语。因此，实际上，两者是没有区别的。

另一方面，如果我在晚上校园里的数学课后与一位数学家交谈，我可能会更加慎重地选择使用特定的术语。因此，在这种情况下，两者是有区别的。

- Bert F

Answer 2

当然有区别。一个有限状态机有限个状态，另一个无限状态机有无限个状态。画无限状态机有些棘手，但是允许有限状态机的数学也将允许无限状态机。

看看FSM的维基百科页面中的“数学模型”部分。看到“S是一个有限的非空状态集合”吗？把“有限”删掉。你的状态转移函数也将变成无限的，但没关系，有很多无限函数。

“From.ME.to.YOU”混淆了维基百科的口头简化和真正的相等宣言。

- Jay Kominek

---

一个具有无限状态的状态机示例：Σ = {-1, 0, 1}。S = Z（整数）。S_0 = 0。δ(s, e) = s+e（这是整数加法）。F={}。你输入-1、0或1，它会跟踪到目前为止所有数字的总和。它永远不会终止。 - Jay Kominek

从你的第二句话可以得出，有限状态机不是状态机，因为OP问题中的“其他”是“状态机”。也就是说，不一定有限就等于无限。 - DSM

好的，说得对。我应该说“一个有限数量的状态，而另一个可能有无限数量的状态。”我承认在数学课上我会被扣掉一些分数。 :) - Jay Kominek

一个非必须有限状态机的例子应该是Kripke自动机。 - Marcin

量子计算机肯定是一个无限状态机吧？ - Jay M

Answer 3

有限状态机（FSM）一词在自动机理论的教科书中有精确定义。 FSM允许以最精确和压缩的方式表示软件实体的行为，因为它们是编程语言和数据表示独立的。 状态机一词常常被宽泛地用来描述“FSM风格”的API集，如Statecharts。遗憾的是，软件工程师很少充分利用FSMs的潜力，因为他们经常受到Statecharts的一系列问题的困扰，例如：非确定性。

- Janusz Dobrowolski

Answer 4

没有。这是我从维基百科引用的：

有限状态机（FSM）或有限状态自动机（复数：automata），简称状态机。

http://en.wikipedia.org/wiki/Finite-state_machine

- trrrrrrm

---

这意味着添加词语“有限”的作用只是语言上的装饰。应该警惕倡导使用简明英语的运动。 - Jay M

Answer 5

假设您不在计算机语言课堂上，在软件上下文中，它几乎总是状态机，因为它不符合FSM（有限状态机）的数学定义。特别是考虑到业务流程管理/工作流时，转换图中的节点数量是有限的，但是过程的状态不受这些限制，并具有无限的外部上下文。

然而，如果有人在软件中提到FSM，指出它不符合数学定义并且他们可能使用该术语来指代简单类型的状态机与Petri网，BPM，编排或任何其他管理状态，过程，转换等的方式相比，这显得有些迂腐。例如，处理管理、持久化状态机和用于解析或网络状态的内存中的状态机之间存在巨大差异。

简而言之，如果您不在课堂上，这非常模糊。

- Spen