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

[pythonee]

[snnn]

吓唬入门的人用的。告诉他们 CS 是个大坑

[misaka19000]

有限状态机是对 if else 的一种实现，最早应该是由图灵提出来的

[purebluesong]

编程语言的本质不也是条件，循环和顺序。那讲那么多 lambda，设计模式，体系结构又有什么意义呢

[stcasshern]

你是说有限状态机的意义？？？一个抽象的模型？不知道怎么解释，但是很有用啊

[rogerchen]

随便一本编译原理书都会告诉你 FA 的本质是三型文法。
这就是传说中的想的太多，读的太少？

[chuanqirenwu]

有限状态机与正则语言等价。if else 是正则语言的一个子集，所以有限状态机可表示的状态多余 if else 可表示的状态。

[noli]

很显然不是。FSM （ Finite state machine ） 和 if-else 完全不是同一个层面的问题。

正确地理解 FSM 的意义是，
能够把有限个变量描述的状态变化过程，以可构造可验证的方式呈现出来。

譬如说，FSM 通常可以用用封闭的有向图来表示。
如果不用这个概念的话，你就没法保证是不是能用这个方法来做。

[noli]

@noli 手抖了。补充一句，

if-else 只能是分支，连闭环都没法做到。
比 FSM 的能力差远了。

[abcbuzhiming]

@chuanqirenwu 很感谢，自我我知道有限状态机这个概念以来头一次弄明白这东西真的由来，但是我想知道两点：

有限状态机（正则语言）能表示的状态多余 if else，这是什么意思，难以想象
这部分知识，属于什么领域（比如程序语言，比如计算机体系，还是别的什么）

[troywinter]

@abcbuzhiming 离散数学里没有讲过有限状态机么？

[monsoon]

@abcbuzhiming 计算理论。

[monsoon]

@chuanqirenwu 我觉得你的说法（ if else 是正则语言的一个子集）是错的。
if else 可以有嵌套结构，因为正则语言解析不了嵌套的结构。所以 if else 肯定不是正则语言的子集。

[abcbuzhiming]

@noli 你这样说我感觉更模糊了，FSM 是否能用编程语言进行实现呢，还是说它仅仅是个概念模型？

[abcbuzhiming]

@troywinter 还真没去学过离散数学

[pythonee]

@rogerchen 确实需要补充

[pythonee]

@noli
@chuanqirenwu
谢谢以上同学的指点，基础知识还是要补下呀

[Shura]

if else or switch case 是实现，fsm 是理论。

[am241]

cpu 可以理解成有限状态机

[feather12315]

if-else 我觉得是 cfg （上下文无关文法，2 型文法）。
因为词法分析中，if-else 可以用 cfg 实现。

[feather12315]

什么是有限状态机？这个问题…
老师上课给了这几个例子：
{ a^n b^n c^n | n >= 1 } 上下文有关文法，csl，1 型文法
{ a^m b^m c^n | m,n >= 1 } 上下文无关文法，cfl，2 型文法
{ a^k b^m c^n | k,m,n >= 1 } 有限自动机，3 型文法

注意 2 型文法与 3 型文法的区别：多了 m。 这可以理解为记忆性，是靠下推栈来实现的（ 3 型文法是 2 型文法的真子集）。

有限状态机的实现，实现就是正则表达式。是将 3 型文法转换为 NFA （不确定有限状态机）或者 DFA （确定有限状态机）。数学上可以证明 NFA 与 DFA 是等价的，但根据<<精通正则表达式>>这书的观点，在效果上他俩还是不一样的。

编译原理，语法分析（就是在讲上下文无关文法）后语法制导的翻译，有一章节内容在讲 if-else 的翻译。我是根据这点判断 if-else 属于上下文无关文法的。（如有错误请指正）。

其实，目前的所有计算机语言都可以说是上下文无关文法。但是它的超集：因为上下文无关文法无法解决--1.变量声明，2.函数参数检查这样的问题。实际上怎么实现？
老师在课上提到了符号表的一个作用：把上下文无关文法无法做到的事情放在语义分析里面做，这俩工作就是通过符号表在语义分析里面完成的。