自动机理论已死？

Question

我非常喜欢学习自动机理论和形式语言课程，因此我自然而然地开始在互联网上寻找有关这门课程所基于的书籍出版以来的最新进展。

但我发现，我不熟悉的内容似乎很少。例如，从维基百科条目中列出的自动机清单中，一半已经在这门课程中涉及到了，而另外一半则主要与未被课程覆盖的一种语言相关。

此外，当我探究该理论的应用时，大多数结果都是：编程语言语法、编译器、文本搜索等，没有其他更多的内容。

那么，这门课程真的已经死了吗？还是说它正在继续发展？这个理论是否有新的应用呢？

- EpsilonVector

---

它并没有死，只是在休息。盼望着回到峡湾。 - fmark

@Hamish Grubijan - 我会成为那里的Jon Skeet ;) - Aiden Bell

一种想法：考虑到这个问题引起的热情程度（通过点赞暗示），也许有足够的兴趣来保持它的开放，即使它与编程没有直接关系？也许我仍然受到学术环境的影响，但我认为偶尔向我们领域的理论根源致以一些敬意是合理的。 - EpsilonVector

关于自动机理论是否属于编程领域的混淆令人惊讶，这表明这是一个不被充分理解的话题。自动机是建模和解决实际问题的一种方式，与算法设计、选择正确的数据结构或理解虚拟内存操作一样重要。这些主题在 Stack Overflow 上都有涉及并且我在大学里也学过，难道它们只适用于学术界吗？ - mdma

认为这个问题不符合主题的人不应该在专业程序员领域工作。 - Michael Borgwardt

Answer 1

自动机非常有用。我将近20年前完成了软件工程和计算机科学的学位，其中第一门课程是机器模型，涵盖了有限状态自动机，以及探究了图灵机，可计算性，停机问题等。

当时，大家都认为这门课程要么枯燥无味，要么与实际无关，要么太难以及毫无意义。对于所有人来说，圆圈和弧形线条几乎没有任何意义，而只由数字“1”组成的纸带有什么用呢？硬盘不好吗？在课程结束时，讲师发放了一份问卷——你认为这门课程在一个月内、一年内和十年内会有多少用处。当时，我回答说对于所有情况都没有用。现在，它随着时间的推移越来越有用，最终回答变成了“非常有用”

我在日常工作中经常使用自动机，并且它们是某些类别的问题的正确工具，几乎没有其他竞争者。我曾经用它们压缩了数百万单词列表和类别数据（好吧，相当平凡），并且还实现了一种扩展，其中符号是复杂对象，状态转换是谓词。这样可以将一组复杂规则编译成确定性有限状态自动机，并同时且无冗余计算地评估所有规则。

我的投票是仍然相关！

- mdma

Answer 2

自动机与形式语言是正则表达式、解析器、编译器、虚拟机等技术的基础，这些技术在不断地进步。

在程序检查领域中，定理证明器需要使用它们，旨在证明程序或协议实现了其所声称的功能。此领域至关重要（如投票机软件、银行交易、车辆安全系统等），目前仍在发展中。

因此，自动机理论和形式语言并没有死亡！

- kabado

Answer 3

它并没有消失，更像是“走向封存”——它是一个简单的形式化方法，更多地被用作他人研究的基础，而不是一个特别活跃的研究话题。

Henry Thompson 在 XML 模式方面的工作使用并扩展了自动机理论。

许多嵌入式软件项目广泛使用有限状态机，这与自动机有关，一些处理这些状态机的技术也在自动机理论上进行了拓展。

Pi-calculus 使用模仿关系的概念扩展了自动机理论，并增加了分析并发进程的功能。它是我在大学学习的自动机理论中最接近的最新研究领域。

- Pete Kirkham

Answer 4

我认为随着计算机领域的新技术，如量子计算和超级计算的出现，将会有新的应用需求，这些需求需要自动机理论、进化自动机和计算、细胞自动机等方面的广泛理论支持。

我不认为它已经死了，只是暂时有些冷淡。

- Aiden Bell

Answer 5

我认为自动机理论在很多领域都有应用，但人们并没有意识到。例如，我可以看到它在密码学和密码分析中的应用。

- Anthony

---

这是事实。但那不是问题所在。许多数学是间接使用的... - Mitch Wheat

是的，自动机理论一点也不过时！它一直被广泛应用！ - Anthony

Answer 6

许多过程控制的内容都严重基于理论。尤其是在证明控制系统的稳健性方面。

- Keith Nicholas

Answer 7

看看工作流程，并了解自动机理论如何在正式描述所述概念和模式方面得到运用：工作流程模式

- Khorkrak

Answer 8

我在几年前接触到的新技术之一叫做解析表达式语法，也称为 PEGs 或 Packrat Parsing。Bryan Ford 在这方面做了一些工作，可以在 http://pdos.csail.mit.edu/~baford/packrat/ 上查看。

这基本上是一种自顶向下递归下降解析器，其优点之一是可以在一步中执行词法分析和语义分析。

PEGs 与 CFGs 相比，更适合解析无上下文语言，而 CFGs 更适合生成无上下文语言。

- Umar Farooq Khawaja

---

我不太确定这与自动机有什么关系，除了 PEGs 不适合任何形式理论之外。从数学角度来看，它们真的是一种非常棘手的构造。有用但很麻烦。还值得注意的是另外两点。首先，PEGs 与 Packrat 解析器不同（Packrat 解析器是记忆化的，而 PEGs 不是）。其次，CFGs 对 PEGs 的单行评估相当主观且有些不连贯（PEG 是一种解析算法，CFG 是一种数学形式主义）。 - Daniel Spiewak

我强烈不同意丹尼尔的观点。PEG是一种形式主义。像其他任何形式主义一样，它是有限制和局限性的，但完全是一种形式主义。实际上，你几乎找不到一个不是形式主义的算法。 - SK-logic

是的，从PEG到自动机有一个明确定义的映射。无限前瞻并不会使它太困难。 - SK-logic

@SK-logic 我要对声称的从PEG到自动机理论的映射提出“需要引用”的质疑。 显然，您可以为PEG接受问题定义一个图灵识别器，但据我所知，理论家们迄今为止一直未能清晰地定义PEG所接受的语言类。 作为这些前述理论家之一，我肯定会对沿着这些方向取得的任何进展感兴趣。 - Daniel Spiewak

@Umar Packrat解析器接受的语言类别比PEG更广泛。其中最主要的例子是左递归。普通的PEG可以处理一些非常特定形式的左递归。而普通的Packrat解析器则能够处理更大量级的左递归规则，并且通过一点技巧，它们可以处理任何形式的非隐藏左递归。这就意味着记忆化PEG（Packrat解析器）至少（并且可能严格）比普通PEG更强大。 - Daniel Spiewak

Answer 9

与其认为理论已经死亡，不如考虑它变得如此实用，以至于我们已经超越了理论。一本很好的书，可以作为理论和应用之间的桥梁，是Miro Samek的“ Practical Statecharts in C/C++”。现在有第二版可用，我还没有看过。但我觉得第一版没有任何缺陷；直到今天，我仍然认为这是我读过的最有价值的文本之一。

- Brent Arias