我喜欢我学习的自动机理论和形式语言课程，所以我很自然地开始浏览互联网，了解自从编写该课程所依据的书籍以来发生的事情。
我发现我不熟悉的东西清单似乎很短。例如，从该主题的 Wikipedia 条目中的自动机列表中，课程涵盖了一半，而另一半则主要与课程未涵盖的一种语言有关。
此外，在研究该理论的应用时，我得到了几乎相同的结果：编程语言语法、编译器、文本搜索等等。
那么它真的死了吗？还是会继续发展？该理论有新的应用吗？
问问题
5278 次
9 回答
19
自动机真的很有用。近 20 年前，我完成了软件工程和计算机科学学位。最早的课程之一是机器模型，它涵盖了 FSA，并在车削机器、可计算性、停机问题等方面进行了一些尝试。
每个人都认为这门课要么无聊、无关紧要、太难，要么毫无意义。圆圈和弧线对任何人来说都毫无意义，而只有一个磁带的磁带有什么意义呢？硬盘有什么问题？课程结束时，讲师发了一份问卷——你认为这门课程在一个月、一年、十年后会有多大用处。然后，我回答不是对所有人都有用。现在它会随着时间的推移而增加有用性，以“非常有用”结尾
我在日常工作中使用了很多自动机，它们是解决某些类别问题的正确工具，几乎没有其他东西可以与之竞争。我已经用它们来压缩数百万个单词列表+类别数据（好吧，相当平庸），并且还实现了一个扩展，其中符号是复杂的对象，状态转换是谓词。这允许将一组复杂的规则编译为确定性 FST，并且所有规则同时且确定性地评估，而无需进行冗余计算。
我的投票仍然有意义！
于 2010-06-04T00:57:43.110 回答
4
自动机和形式语言是定期改进的正则表达式、解析器、编译器、虚拟机等的基础。
在定理证明器领域也需要程序检查，其目的是证明程序或协议实现了它假装做的事情。这个领域很关键（投票机软件、银行交易、车载安全系统等）并且仍在开发中。
所以不，自动机理论和形式语言并没有死！
于 2010-06-04T08:05:44.490 回答
3
它并没有死，更多的是“投入研究”——它是一种简单的形式主义，更多地被用作其他人的基础，而不是一个特别活跃的研究课题。
Henry Thompson在 XML 模式方面的工作使用并扩展了自动机理论。
许多嵌入式软件项目大量使用与自动机相关的有限状态机，并且使用它们的一些技术借鉴或扩展了自动机理论。
Pi-演算用互模拟的概念扩展了自动机理论，并增加了分析并发过程的能力。这是我最近在大学学到的最接近自动机理论的研究。
于 2010-06-04T07:38:33.023 回答
1
我认为自动机理论涉及很多领域，而人们却没有意识到。例如，我可以看到它在密码学和密码分析中的应用。
于 2010-06-04T00:52:22.357 回答
0
很多过程控制的东西都是基于理论的。特别是在证明控制系统的鲁棒性方面。
于 2010-06-04T00:55:21.317 回答
0
看看工作流过程，看看如何将自动机理论用于形式化所描述的概念和模式：工作流模式
于 2010-06-04T00:57:20.833 回答
0
几年前我遇到的一种新技术叫做解析表达式语法，又名 PEGs 又名 Packrat Parsing。Bryan Ford 已经完成了一些工作，可以在http://pdos.csail.mit.edu/~baford/packrat/查看。
这基本上是一个自顶向下的递归下降解析器，它的优点之一是词法分析和语义分析可以一步完成。
PEG 与 CFG 相比，PEG 更适合解析上下文无关语言，而 CFG 更适合生成上下文无关语言。
于 2010-06-04T02:00:46.977 回答
0
与其认为该理论已死，不如考虑它已经变得如此实用，以至于我们已经超越了该理论。Miro Samek 的“ C/C++ 中的实用状态图”是一本很好的书，可以考虑理论和应用之间的桥梁。现在有第二版，我还没读过。但我发现第一版没有任何不足之处。直到今天，我发现它是我读过的最有价值的文本之一。
于 2010-06-04T02:06:54.977 回答