我非常喜欢学习自动机理论和形式语言课程,因此我自然而然地开始在互联网上寻找有关这门课程所基于的书籍出版以来的最新进展。
但我发现,我不熟悉的内容似乎很少。例如,从维基百科条目中列出的自动机清单中,一半已经在这门课程中涉及到了,而另外一半则主要与未被课程覆盖的一种语言相关。
此外,当我探究该理论的应用时,大多数结果都是:编程语言语法、编译器、文本搜索等,没有其他更多的内容。
那么,这门课程真的已经死了吗?还是说它正在继续发展?这个理论是否有新的应用呢?
我非常喜欢学习自动机理论和形式语言课程,因此我自然而然地开始在互联网上寻找有关这门课程所基于的书籍出版以来的最新进展。
但我发现,我不熟悉的内容似乎很少。例如,从维基百科条目中列出的自动机清单中,一半已经在这门课程中涉及到了,而另外一半则主要与未被课程覆盖的一种语言相关。
此外,当我探究该理论的应用时,大多数结果都是:编程语言语法、编译器、文本搜索等,没有其他更多的内容。
那么,这门课程真的已经死了吗?还是说它正在继续发展?这个理论是否有新的应用呢?
自动机非常有用。我将近20年前完成了软件工程和计算机科学的学位,其中第一门课程是机器模型,涵盖了有限状态自动机,以及探究了图灵机,可计算性,停机问题等。
当时,大家都认为这门课程要么枯燥无味,要么与实际无关,要么太难以及毫无意义。对于所有人来说,圆圈和弧形线条几乎没有任何意义,而只由数字“1”组成的纸带有什么用呢?硬盘不好吗?在课程结束时,讲师发放了一份问卷——你认为这门课程在一个月内、一年内和十年内会有多少用处。当时,我回答说对于所有情况都没有用。现在,它随着时间的推移越来越有用,最终回答变成了“非常有用”
我在日常工作中经常使用自动机,并且它们是某些类别的问题的正确工具,几乎没有其他竞争者。我曾经用它们压缩了数百万单词列表和类别数据(好吧,相当平凡),并且还实现了一种扩展,其中符号是复杂对象,状态转换是谓词。这样可以将一组复杂规则编译成确定性有限状态自动机,并同时且无冗余计算地评估所有规则。
我的投票是仍然相关!
自动机与形式语言是正则表达式、解析器、编译器、虚拟机等技术的基础,这些技术在不断地进步。
在程序检查领域中,定理证明器需要使用它们,旨在证明程序或协议实现了其所声称的功能。此领域至关重要(如投票机软件、银行交易、车辆安全系统等),目前仍在发展中。
因此,自动机理论和形式语言并没有死亡!
它并没有消失,更像是“走向封存”——它是一个简单的形式化方法,更多地被用作他人研究的基础,而不是一个特别活跃的研究话题。
Henry Thompson 在 XML 模式方面的工作使用并扩展了自动机理论。
许多嵌入式软件项目广泛使用有限状态机,这与自动机有关,一些处理这些状态机的技术也在自动机理论上进行了拓展。
Pi-calculus 使用模仿关系的概念扩展了自动机理论,并增加了分析并发进程的功能。它是我在大学学习的自动机理论中最接近的最新研究领域。
我认为自动机理论在很多领域都有应用,但人们并没有意识到。例如,我可以看到它在密码学和密码分析中的应用。
我在几年前接触到的新技术之一叫做解析表达式语法,也称为 PEGs 或 Packrat Parsing。Bryan Ford 在这方面做了一些工作,可以在 http://pdos.csail.mit.edu/~baford/packrat/ 上查看。
这基本上是一种自顶向下递归下降解析器,其优点之一是可以在一步中执行词法分析和语义分析。
PEGs 与 CFGs 相比,更适合解析无上下文语言,而 CFGs 更适合生成无上下文语言。