谁能帮我捋一下自动机和算法这两个概念？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 545 天前的主题，其中的信息可能已经有所发展或是发生改变。

我最近在看编译原理的书。
在词法分析这一章经常写构造有限自动机来实现 scanner 。
在我看来这不就是某个算法吗？

然后我又在知乎上看到这个问题。
算法、自动机理论、形式语言、可计算性理论之间都是什么关系？ https://www.zhihu.com/question/28932188

但是这些回答就像黑话一样，看完了我更蒙蔽了。
求大神指点一下。

自动机

算法

黑话

词法

10 条回复 • 2023-05-31 09:26:21 +08:00

DenseHazy

2023-05-30 17:46:20 +08:00

希望这个视频有所帮助 https://www.bilibili.com/video/BV1Ms411A7EP?p=14

009694

2023-05-30 17:47:52 +08:00 via iPhone

算法用于描述和解决问题的具体步骤，形式语言是用来描述算法的工具，自动机用于实现和理解算法的模型，可计算性理论则是用来界定算法可能和不可能达到的范围。

Kumo31

2023-05-30 18:17:19 +08:00

2 楼说的比较清楚了，在我看来还有一个区别是他们的研究目的不同。算法研究通常是为了利用计算机解决某一类问题，这就需要知道什么是计算机，怎么抽象计算机。自动机就是计算的数学模型，属于计算理论的一部分，是为了抽象和研究计算机本身的基本能力

Saitama

2023-05-30 18:43:50 +08:00

@009694 @Kumo31
我用大白话来说一下我的理解。
比方说我作为一个编程小白，没读过编译原理的书，也可以写出一个简单的 Scanner 。比如简单的 int, variable 识别，指需要 if else 判断+循环即可。这可以看作是一个算法。
但是当词法变的复杂，比如识别不同进制的整数，整数的后缀等，这时候程序就很难写，即便写出来可读性和可维护性也不好。
于是有人抽象出了 NFA, DFA 这些模型，还有他们之间的转换算法。这样不管程序的词法变得多复杂，不管我们的程序有多复杂，我们都可以通过 DFA ，来读懂或者维护这个程序。
也就是“自动机用于实现和理解算法的模型”。

这样理解对吗？

goldiorl

2023-05-30 19:24:46 +08:00

@Saitama 看主题还以为楼主已经知道了一点了,看最新的回答感觉楼主搞混了，混成这样了建议问 Bing chat

算法和计算机没有关系,跟实现没有关系,你可以理解为算法是数学层面的对解决问题步骤的描述.

说白了算法更抽象,包含的范围更大

你说得"构造有限自动机来实现 scanner"是种算法,这句话某种意义上讲是正确的,他是一个具体的算法

可计算理论是讲算法能否被现有计算机架构实现的.

至于自动机,下推自动机,图灵机,是可计算理论里面讨论可计算架构的理论模型

冯诺依曼架构是实现,可实现上述所有模型