自动机与形式语言

自动机与形式语言理论研究能力不断增强的理想化机器，以及每种机器能够识别的字符串或语言类别，从而精确地数学描述了什么是模式以及检测模式所需的方法。

Definition

形式语言是固定字母表上有限字符串的集合，而自动机是一种抽象的计算设备，其接受计算定义了这样一种语言；该领域根据生成或识别它们的自动机或文法最简单的类型对语言进行分类。

Scope

该领域涵盖有限自动机和正则语言、下推自动机和上下文无关语言、将文法与机器模型联系起来的乔姆斯基谱系、语言类别的封闭性和判定性质，以及处理无限词和树的自动机，同时还包括伴随它们的代数和逻辑特征。

Sub-topics

• 无限对象上的自动机
• 上下文无关语言和下推自动机
• 有限自动机与正则语言
• 乔姆斯基谱系

Core questions

• 具有有限内存的机器可以识别哪些语言，又不能识别哪些语言？
• 在乔姆斯基谱系的各个层次上，文法和机器模型如何对应？
• 关于语言类别的问题，例如空性或等价性，哪些是算法可判定的？
• 自动机如何扩展到无限词和树，这对于验证为何重要？

Key theories

确定性有限自动机与非确定性有限自动机的等价性

每个非确定性有限自动机都可以通过子集构造转换为接受相同语言的确定性有限自动机，因此，尽管非确定性在有限状态级别上可以指数级地更简洁，但它并没有增加识别能力。

克莱尼定理

有限自动机识别的语言正是正则表达式描述的正则语言，这使得最简单语言类别的机器、代数和文法观点得以结合。

乔姆斯基谱系

正则语言、上下文无关语言、上下文相关语言和递归可枚举语言形成一个严格的包含链，每个级别都与一种文法类型和一种具有相应内存结构的自动机模型相匹配。

Clinical relevance

有限自动机和正则表达式为编译器中的词法分析、文本搜索和协议规范提供了动力，而上下文无关文法则构成了编程语言解析的基础；无限对象上的自动机构成了模型检验的算法核心，其中系统根据时序逻辑规范进行验证。

History

有限状态模型起源于麦卡洛克和皮茨在20世纪40年代提出的神经网络，并于1951年左右由克莱尼赋予了语言理论形式。拉宾和斯科特于1959年引入了非确定性自动机，而乔姆斯基在20世纪50年代后期提出的文法将语言类别组织成至今仍构成该学科结构的谱系。

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Noam Chomsky

Seminal works

• rabinScott1959
• sipser2013
• hopcroft2006

Frequently asked questions

为什么有限自动机无法识别平衡括号？

识别任意深度的嵌套需要计算有多少个未匹配的左括号，这可能会超出任何固定数量的状态。有限自动机只有有限的内存，因此这种计数能力属于更高一个级别，即下推自动机和上下文无关语言。

形式语言理论的实际意义是什么？

它告诉工程师给定工具可以表达哪些模式。正则表达式足以处理词元，但不足以处理嵌套结构，这就是为什么编译器将工作分为正则词法分析器和上下文无关解析器，以及为什么验证工具依赖于无限词上的自动机。