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

[Saitama]

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

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

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

[DenseHazy]

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

[009694]

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

[Kumo31]

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

[Saitama]

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

这样理解对吗？

[goldiorl]

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

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

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

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

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

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

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

[tyzandhr]

自动机是实在的，算法只是概念

[leonshaw]

@Saitama
词法分析里讨论的自动机是一类解决具体问题的自动机。计算理论里讨论的是更抽象的自动机全体。

[mobpsycho100]

这确实是个算法呀，这个算法构造了一个自动机，读取字符串然后运行这个自动机，最后处理运行结果。至于自动机是不是算法？从定义上看，算法至少得是指令的序列，所以自动机不是算法。建议去 Wikipedia 看看两者的定义。

[Saitama]

@mobpsycho100 你这个说法挺通俗易懂的，谢谢！

[SmiteChow]

算法是一个类目，自动机是一个子类