有限状态机的本质是不是也是 if-else，那这个概念的意义在于什么呢

[pythonee]

[feather12315]

@am241 能详细讲一下吗

[noli]

@abcbuzhiming

FSM 是否能用编程语言进行实现呢？

当然能。
各种 VM，什么 JVM，PVM，LuaVM 就是一种抽象了物理设备的状态机，纯粹用编程语言实现的。
一个正则表达式引擎也是一个纯粹用编程语言实现的状态机。

只不过实现这些 VM 也好，引擎也好，其作者当时是不是必须要有一个状态机的概念？
不一定，它确实就只是一个概念模型。

[watzds]

归根结底不都是 0 和 1😂

[geelaw]

并不知道你说的 if-else 是什么意思😮这个问题不是 well-asked

[DaPanda]

楼主疑惑的应该是，FSM 的转移函数就好像是层层嵌套的 if-else 语句一样，如果符合某个条件，那么跳转至某个状态。所以他想问这两者有什么不一样。

如果楼主说的 if-else 是一般编程语言中的 if-else 语句，那么 if-else 是内存地址的跳转，而内存又是冯诺依曼对图灵机模型的实现中的一部分。这种情况下前边有人也回答了一个是模型一个是实现。所以这两者之间没有可比性。

但如果楼主问的 if-else 只是我们一般逻辑认知上的 if-else，那么人作为计算模型至少是在图灵机级别的，这种情况下非要比的话我觉得 if-else 是强于 FSM 的。

[RqPS6rhmP3Nyn3Tm]

扯一句，Verilog 写得我想死

[GoForce5500]

从软件工程的角度看，封装逻辑。

[holy_sin]

为了装逼吗

[chuanqirenwu]

@monsoon 嗯，看到下面的朋友有详细解释，if else 属于上下文无关文法。那这么看来岂不是楼主是对的，上下文无关文法包含正则语言。那 if else 可以表述任何有限状态机。

[HowardMei]

@abcbuzhiming 有限状态机是从逻辑学直接导出的，比抽象算法底层多了，状态机是数字电路的基本设计单元，能接受时钟的时序控制。

If/else/case/switch 仅相当于状态机里的 Mux(选择器)，主要用途是选址，或参与编解码，干不了存储、计算等活。

有向图是同步时域状态机的简化抽象，也可以用真值表表示。

[chuanqirenwu]

@abcbuzhiming I am sorry，经 v 友指出我可能有误，不要被我误导。这问题我没有深究，如果想深入研究请参阅一些编译原理以及形式语言和有限自动机的书。

[HowardMei]

@chuanqirenwu 并不能，if/else 不含时序，而状态机包含时序，每次状态转移都意味着一个时钟节拍。

[HowardMei]

@DaPanda 状态机并不能化约为 If/else，首先寄存器之类时序触发逻辑它就表示不了。

不要把有向图当作状态机，它只是一个简化表示，完整表示应该用时序图，实际状态机请参考常见的 Moore & Mealy 型。

[wizardoz]

定理都是由公里可以推导出来的，那么定理的意义何在？

[linjianru]

这是属于自动机理论中的一个主题。可以细分成更多类别，例如确定型的，非确定型的等等，其他还有下推自动机，无限状态自动机等等。

这玩意儿是用来进行计算模型建模的。它可以告诉我们每种类型的计算机其计算能力的边界，以及完成计算所需的复杂程度。所以通常是结合计算复杂性理论一起介绍。

但是它也有很多实际的用途，最典型的就是协议验证。比如 TCP 协议就是转化成了状态机然后验证其完备性的。如果没有这样的理论检查，很难相信它会不会在某些特殊状况（大家都考虑漏了的时候）出现意想不到的问题。

密码学中许多协议也需要进行这样的理论模型验证。其他像文本搜索（包括文法识别）也是状态机的常见应用。

可以说，这是一个很重要的领域。

至于你说的 if/else，其实是个实现层面的问题。这就相当于图纸和实物的关系。就状态机模型而言，它并不关系你是否用 if/else 去实现它，它只关心性质本身。

顺便一提，不使用 if/else 也可以实现分支选择的。在纯函数式编程语言里完全可以把 if/else 定义为一种平凡的布尔函数，二者具有等价的功能。

[HowardMei]

@linjianru 算法类的自动机也不是单纯分支选择，不能化约为 if/else，肯定要有反映时序的步进控制，比如 for/while 或递归。

[1000copy]

@snnn good

[bombless]

有限状态机是用来区分不同的状态机的概念吧

[DaPanda]

@HowardMei 你可能误会我意思了。并不是说状态机可以被简化为 if-else，只是在猜测楼主的疑惑在哪。我觉得他可能是看了一个状态图（或者 formal description ），在疑惑既然本质就是根据条件运行至某个状态，为什么还要提出一个 FSM 的概念。
我觉得楼上几个朋友说的 if-else 是实现，也都不是在说只用 if-else 就能完整实现了—— if-else 显然没有这么大能力。
另外时序图只是对 FSM 另一个角度的描述，从计算模型上没有任何扩展吧。

[HowardMei]

@DaPanda 哦，那是我阅读理解错了😭

时序图包含的信息比有向图完整