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

2023-05-30 17:34:36 +08:00
 Saitama
我最近在看编译原理的书。
在词法分析这一章经常写构造有限自动机来实现 scanner 。
在我看来这不就是某个算法吗?

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

但是这些回答就像黑话一样,看完了我更蒙蔽了。
求大神指点一下。
1874 次点击
所在节点    程序员
10 条回复
DenseHazy
2023-05-30 17:46:20 +08:00
009694
2023-05-30 17:47:52 +08:00
算法用于描述和解决问题的具体步骤,形式语言是用来描述算法的工具,自动机用于实现和理解算法的模型,可计算性理论则是用来界定算法可能和不可能达到的范围。
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"是种算法,这句话某种意义上讲是正确的,他是一个具体的算法

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

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

冯诺依曼架构是实现,可实现上述所有模型
tyzandhr
2023-05-30 20:19:32 +08:00
自动机是实在的,算法只是概念
leonshaw
2023-05-30 20:39:39 +08:00
@Saitama
词法分析里讨论的自动机是一类解决具体问题的自动机。计算理论里讨论的是更抽象的自动机全体。
mobpsycho100
2023-05-30 20:56:19 +08:00
这确实是个算法呀,这个算法构造了一个自动机,读取字符串然后运行这个自动机,最后处理运行结果。至于自动机是不是算法?从定义上看,算法至少得是指令的序列,所以自动机不是算法。建议去 Wikipedia 看看两者的定义。
Saitama
2023-05-30 22:21:24 +08:00
@mobpsycho100 你这个说法挺通俗易懂的,谢谢!
SmiteChow
2023-05-31 09:26:21 +08:00
算法是一个类目,自动机是一个子类

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/944276

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX