乔姆斯基谱系的通俗易懂解释

Question

我正在尝试找到一份简明易懂（即非正式）的关于乔姆斯基所提出的四个形式语法层次（无限制文法，上下文有关文法，上下文无关文法，正则文法）的解释。

自我学习形式语法以来已经过了很久，现在各种定义对我来说都很混淆。我想要强调的是，我不是在寻找你可以在任何地方找到的正式定义（例如这里和这里——我和其他人一样可以使用谷歌），甚至不是任何类型的正式定义。相反，我希望找到简洁明了的解释，既清晰易懂又完整。

- tylerl

---

很棒的问题。它应该出现在每一本理论计算机科学书籍中。 - peri4n

@muistooshort，我不确定它是否更适合于cstheory。它可能在那里有些适当，但它肯定适合在这里，属于“编程专业中独特的实际可回答问题”范畴。事实上，就语法分类而言，这个问题更偏向于“实际”一侧，而不是“理论”一侧。我具体询问的是分类在实际方面意味着什么，而不是纯粹的cs-theory术语。 - tylerl

Answer 1

如果您记住自动机生成这些语言，您可能会更好地理解。

正则语言由正则自动机生成。它们只具有过去的有限知识（与计算内存限制相关），所以每当您有一个依赖于前缀的后缀的语言（回文语言），就无法使用正则语言进行处理。

上下文无关语言由非确定性下推自动机生成。它们具有某种有限的过去知识（堆栈，与正则自动机不同，堆栈没有限制），但是堆栈只能从顶部查看，因此您不具有完整的过去知识。

上下文相关语言由线性受限非确定性图灵机生成。它们知道过去并且可以处理不同的上下文，因为它们是非确定性的并且可以在任何时间访问所有过去的内容。

无限制语言由图灵机生成。根据Church-Turing-Thesis，图灵机能够计算您能想象到的一切（这意味着一切可判定的事情）。

- peri4n

---

有限自动机可以记住过去的信息，但只有有限的数量。你对于无上下文语言的解释是不正确的。生成无上下文语言的正确自动机类是非确定性下推自动机(NPDA)。确定性下推自动机(DPDA)比NPDA弱。"上下文有关语言是由非确定性下推自动机生成的"也是不正确的。NPDA只能生成无上下文语言。 - Prateek

最后一项中的“无限制语言”和“可判定性”术语是错误的，因为由图灵机（或Chomsky Type 0文法）生成的语言是递归可枚举语言（递归可枚举语言类嵌套在所有形式语言类中（没有任何限制），而可判定语言则嵌套在递归可枚举语言中）。 - Thorsten

Answer 2

常规语言：这些语言可以用有限自动机回答是/否问题。

上下文无关语言：当给定输入单词（使用状态机和堆栈）时，我们总是可以回答是/否是否为该语言的成员。

上下文相关语言：只要语法中的产生式不会缩小（α -> β），我们就可以回答是/否（使用状态机和与输入大小成线性关系的一块内存）。

递归可枚举语言：它可以回答是，但在否的情况下将进入无限循环。

请参见此视频以获取完整说明。

- user93

Answer 3

关于正则语言，有许多等价的描述方式。它们提供了很多不同的看待正则语言的方法。很难给出一个“通俗易懂”的定义，如果你发现难以理解任何一个正则语言的特征描述，那么一个“通俗易懂”的解释也是无济于事的。从定义和各种封闭性质中可以注意到的一点是，正则语言在某种程度上体现了“有限性”的概念。但是，如果没有更好地熟悉正则语言，这也很难理解。

你觉得有限自动机的概念不简单、不清晰吗？

让我提一下许多等价的描述方式（至少对其他读者而言）。

• 确定性有限自动机所接受的语言
• 非确定性有限自动机所接受的语言
• 交替有限自动机所接受的语言
• 双向确定性有限自动机所接受的语言
• 左线性文法所生成的语言
• 右线性文法所生成的语言
• 正则表达式所生成的语言
• 一个 有限指数右同余 的某些等价类的并集。
• 有限指数同余下的某些等价类的并集。
• 在有限单词上的单调第二阶逻辑表达的语言。

- Prateek

---

他说他不需要正式定义，他想知道的是……正式定义。 - peri4n