这是一个创建于 2704 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
snnn 2017-07-02 21:47:52 +08:00
吓唬入门的人用的。告诉他们 CS 是个大坑
|
 |
2
misaka19000 2017-07-02 21:48:39 +08:00
有限状态机是对 if else 的一种实现，最早应该是由图灵提出来的
|
 |
3
purebluesong 2017-07-02 21:50:34 +08:00 via Android
编程语言的本质不也是条件，循环和顺序。那讲那么多 lambda，设计模式，体系结构又有什么意义呢
|
 |
4
stcasshern 2017-07-02 21:54:16 +08:00
你是说有限状态机的意义？？？一个抽象的模型？不知道怎么解释，但是很有用啊
|
 |
5
rogerchen 2017-07-02 21:56:28 +08:00
随便一本编译原理书都会告诉你 FA 的本质是三型文法。
这就是传说中的想的太多，读的太少？ |
 |
6
chuanqirenwu 2017-07-02 22:34:38 +08:00  1
有限状态机与正则语言等价。if else 是正则语言的一个子集，所以有限状态机可表示的状态多余 if else 可表示的状态。
|
 |
7
noli 2017-07-02 22:51:30 +08:00 2
很显然不是。FSM （ Finite state machine ） 和 if-else 完全不是同一个层面的问题。
正确地理解 FSM 的意义是， 能够把有限个变量描述的状态变化过程，以可构造可验证的方式呈现出来。 譬如说，FSM 通常可以用用封闭的有向图来表示。 如果不用这个概念的话，你就没法保证是不是能用这个方法来做。 |
 |
9
abcbuzhiming 2017-07-02 23:20:13 +08:00
@chuanqirenwu 很感谢，自我我知道有限状态机这个概念以来头一次弄明白这东西真的由来，但是我想知道两点：
有限状态机（正则语言）能表示的状态多余 if else，这是什么意思，难以想象 这部分知识，属于什么领域（比如程序语言，比如计算机体系，还是别的什么） |
 |
10
troywinter 2017-07-02 23:28:15 +08:00
@abcbuzhiming 离散数学里没有讲过有限状态机么？
|
 |
11
monsoon 2017-07-02 23:30:38 +08:00 via Android
@abcbuzhiming 计算理论。
|
|
12
monsoon 2017-07-02 23:38:54 +08:00 via Android
@chuanqirenwu 我觉得你的说法（ if else 是正则语言的一个子集）是错的。
if else 可以有嵌套结构，因为正则语言解析不了嵌套的结构。所以 if else 肯定不是正则语言的子集。 |
|
13
abcbuzhiming 2017-07-02 23:46:06 +08:00
@noli 你这样说我感觉更模糊了，FSM 是否能用编程语言进行实现呢，还是说它仅仅是个概念模型？
|
|
14
abcbuzhiming 2017-07-02 23:46:25 +08:00
@troywinter 还真没去学过离散数学
|
 |
16
pythonee OP |
 |
17
Shura 2017-07-03 00:37:46 +08:00 via Android
if else or switch case 是实现，fsm 是理论。
|
 |
18
am241 2017-07-03 00:46:13 +08:00 via Android
cpu 可以理解成有限状态机
|
 |
19
feather12315 2017-07-03 00:58:54 +08:00 via Android
if-else 我觉得是 cfg （上下文无关文法，2 型文法）。
因为词法分析中，if-else 可以用 cfg 实现。 |
|
20
feather12315 2017-07-03 01:15:03 +08:00 via Android 2
什么是有限状态机？这个问题…
老师上课给了这几个例子： { 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.函数参数检查这样的问题。实际上怎么实现？ 老师在课上提到了符号表的一个作用：把上下文无关文法无法做到的事情放在语义分析里面做，这俩工作就是通过符号表在语义分析里面完成的。 |
|
21
feather12315 2017-07-03 01:15:45 +08:00 via Android
@am241 能详细讲一下吗
|
|
22
noli 2017-07-03 01:57:45 +08:00 1
@abcbuzhiming
FSM 是否能用编程语言进行实现呢？ 当然能。 各种 VM，什么 JVM，PVM，LuaVM 就是一种抽象了物理设备的状态机，纯粹用编程语言实现的。 一个正则表达式引擎也是一个纯粹用编程语言实现的状态机。 只不过实现这些 VM 也好，引擎也好，其作者当时是不是必须要有一个状态机的概念？ 不一定，它确实就只是一个概念模型。 |
 |
23
watzds 2017-07-03 02:11:42 +08:00 via Android
归根结底不都是 0 和 1😂
|
 |
24
geelaw 2017-07-03 02:24:22 +08:00 via Android
并不知道你说的 if-else 是什么意思😮这个问题不是 well-asked
|
 |
25
DaPanda 2017-07-03 05:46:41 +08:00 1
楼主疑惑的应该是，FSM 的转移函数就好像是层层嵌套的 if-else 语句一样，如果符合某个条件，那么跳转至某个状态。所以他想问这两者有什么不一样。
如果楼主说的 if-else 是一般编程语言中的 if-else 语句，那么 if-else 是内存地址的跳转，而内存又是冯诺依曼对图灵机模型的实现中的一部分。这种情况下前边有人也回答了一个是模型一个是实现。所以这两者之间没有可比性。 但如果楼主问的 if-else 只是我们一般逻辑认知上的 if-else，那么人作为计算模型至少是在图灵机级别的，这种情况下非要比的话我觉得 if-else 是强于 FSM 的。 |
 |
26
RqPS6rhmP3Nyn3Tm 2017-07-03 08:16:02 +08:00
扯一句，Verilog 写得我想死
|
 |
27
GoForce5500 2017-07-03 08:36:09 +08:00
从软件工程的角度看，封装逻辑。
|
 |
28
holy_sin 2017-07-03 09:30:58 +08:00
为了装逼吗
|
|
29
chuanqirenwu 2017-07-03 09:37:19 +08:00
@monsoon 嗯，看到下面的朋友有详细解释，if else 属于上下文无关文法。那这么看来岂不是楼主是对的，上下文无关文法包含正则语言。那 if else 可以表述任何有限状态机。
|
 |
30
HowardMei 2017-07-03 09:39:11 +08:00 via Android
@abcbuzhiming 有限状态机是从逻辑学直接导出的，比抽象算法底层多了，状态机是数字电路的基本设计单元，能接受时钟的时序控制。
If/else/case/switch 仅相当于状态机里的 Mux(选择器)，主要用途是选址，或参与编解码，干不了存储、计算等活。 有向图是同步时域状态机的简化抽象，也可以用真值表表示。 |
|
31
chuanqirenwu 2017-07-03 09:39:31 +08:00
@abcbuzhiming I am sorry，经 v 友指出我可能有误，不要被我误导。这问题我没有深究，如果想深入研究请参阅一些编译原理以及形式语言和有限自动机的书。
|
|
32
HowardMei 2017-07-03 09:41:40 +08:00 via Android 2
@chuanqirenwu 并不能，if/else 不含时序，而状态机包含时序，每次状态转移都意味着一个时钟节拍。
|
|
33
HowardMei 2017-07-03 09:46:12 +08:00 via Android
@DaPanda 状态机并不能化约为 If/else，首先寄存器之类时序触发逻辑它就表示不了。
不要把有向图当作状态机，它只是一个简化表示，完整表示应该用时序图，实际状态机请参考常见的 Moore & Mealy 型。 |
 |
34
wizardoz 2017-07-03 09:50:42 +08:00
定理都是由公里可以推导出来的，那么定理的意义何在？
|
 |
35
linjianru 2017-07-03 10:06:50 +08:00 2
这是属于自动机理论中的一个主题。可以细分成更多类别，例如确定型的，非确定型的等等，其他还有下推自动机，无限状态自动机等等。
这玩意儿是用来进行计算模型建模的。它可以告诉我们每种类型的计算机其计算能力的边界，以及完成计算所需的复杂程度。所以通常是结合计算复杂性理论一起介绍。 但是它也有很多实际的用途，最典型的就是协议验证。比如 TCP 协议就是转化成了状态机然后验证其完备性的。如果没有这样的理论检查，很难相信它会不会在某些特殊状况（大家都考虑漏了的时候）出现意想不到的问题。 密码学中许多协议也需要进行这样的理论模型验证。其他像文本搜索（包括文法识别）也是状态机的常见应用。 可以说，这是一个很重要的领域。 至于你说的 if/else，其实是个实现层面的问题。这就相当于图纸和实物的关系。就状态机模型而言，它并不关系你是否用 if/else 去实现它，它只关心性质本身。 顺便一提，不使用 if/else 也可以实现分支选择的。在纯函数式编程语言里完全可以把 if/else 定义为一种平凡的布尔函数，二者具有等价的功能。 |
|
36
HowardMei 2017-07-03 10:53:48 +08:00 via Android
@linjianru 算法类的自动机也不是单纯分支选择，不能化约为 if/else，肯定要有反映时序的步进控制，比如 for/while 或递归。
|
 |
38
bombless 2017-07-03 10:58:48 +08:00
有限状态机是用来区分不同的状态机的概念吧
|
|
39
DaPanda 2017-07-03 11:23:17 +08:00
@HowardMei 你可能误会我意思了。并不是说状态机可以被简化为 if-else，只是在猜测楼主的疑惑在哪。我觉得他可能是看了一个状态图（或者 formal description ），在疑惑既然本质就是根据条件运行至某个状态，为什么还要提出一个 FSM 的概念。
我觉得楼上几个朋友说的 if-else 是实现，也都不是在说只用 if-else 就能完整实现了—— if-else 显然没有这么大能力。 另外时序图只是对 FSM 另一个角度的描述，从计算模型上没有任何扩展吧。 |
|
41
feather12315 2017-07-08 21:03:25 +08:00 via Android
问题一：
我是这么理解正则表达式的：它是有限自动机的一个实现（或者说一个实例）。有限自动机的实现还有 TCP 状态之间的转换。那么，IF-ELSE 这算是上下文无关语法的实现吗？ 我不明白你所谓的实现是什么意思。正则表达式描述了一个语言结构，有限自动机来识别这个语言，正则表达式可以转换为有限自动机，有限自动机运行时和程序差不多，从某种意义上看，正则表达式也就是程序。有限自动机可以认为是一个抽象的模型，具体化下来可以有很多实例，如程序运行，协议运行。同样，if 结构也是一个语言，但是正则表达式描述不了，上下文无关语法可以描述。你所谓的实现，前后含义好像并不一样。在形式化方法中，你要定义实现，才能讨论后续的问题。如果你定义实现为一个实例，那么把有限自动机定义中的 5 元组分别给出来，可以得到很多具体的有限自动机例子，当然可以包含 TCP 转换。同样 CFG 的 4 元组分别给出了，可以得到很多具体的 CFG 例子，当然包含 if 结构。从这个意义上看，正则表达式是有限自动机的一个实现，就是不对的。 问题二： 没记错的话，含有 顺序连接 / 循环(WHILE) / 跳转(IF-ELSE) 这三种连接结构的计算机语言是完备的，这个完备性是怎么证明的呢？能给点相关的资料吗？ 结构化程序设计的思想最早是 Dijkstra 提出的，用 baidu 找“选择 循环 顺序 Dijkstra ”，可以找到相关资料，还有 1966 年 Corrado Böhm 和 Giuseppe Jacopini 给出了证明。这些太老了，实在没有必要浪费时间去看。 我老师的回答= = |
Select Language