形式语言理论与自动机

形式语言理论和识别它们的抽象机器，为描述语言模式的复杂程度以及哪些算法可以处理它提供了词汇。

Definition

形式语言理论研究由文法定义的字符串集合，而自动机理论研究决定这些集合成员资格的抽象机器。

Scope

涵盖乔姆斯基谱系（正则语言、上下文无关语言、上下文相关语言、递归可枚举语言）、相应的文法以及识别自动机——有限状态机、下推自动机和图灵机。它涉及与语言处理相关的闭包和可判定性属性，以及自然语言在谱系中的位置问题。泵引理和完整的复杂性证明被视为背景知识而非主要内容。

Core questions

• 哪种自动机对应乔姆斯基谱系的每个级别？
• 自然语言在谱系中处于何处，为什么有人认为它超越了上下文无关的能力？
• 语言类别在某种操作下闭合意味着什么，为什么这对工程很重要？

Key concepts

• 正则语言
• 上下文无关文法
• 上下文相关文法
• 有限状态自动机
• 下推自动机
• 图灵机
• 闭包属性
• 轻度上下文相关性

Key theories

乔姆斯基谱系

四种嵌套的形式语言类别，每种都由受限的文法类型生成并由相应的自动机识别，根据所需的计算能力对语言结构进行排序。

文法-自动机对应关系

每种文法类别都可证明等同于一种机器类别——正则文法对应有限自动机，上下文无关文法对应下推自动机——将生成描述与识别算法联系起来。

History

乔姆斯基1956年的论文引入了该谱系，作为论证有限状态模型不足以处理自然语言的一部分。随后的几十年形式化了自动机对应关系，计算语言学家后来表明自然语言最多只需要“轻度上下文相关”的能力，从而推动了超越上下文无关文法的形式化。

Debates

自然语言是上下文无关的吗？

瑞士德语等语言中的交叉依赖关系被用来论证自然语言超越了上下文无关的能力，从而引出了轻度上下文相关性作为正确表达能力水平的概念。

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

正则语言和上下文无关语言有什么区别？

正则语言可以通过有限状态自动机以有限内存识别；上下文无关语言可能需要一个栈（下推自动机）来跟踪嵌套结构，例如平衡括号或嵌入式从句。