grammar - 简明英语的乔姆斯基层次结构

Question

我试图找到乔姆斯基提出的 4 级形式语法(无限制、上下文相关、上下文无关、常规)的简单(即非形式)解释。

自从我学习形式语法以来已经过去了一个时代，现在各种定义让我难以想象。明确地说，我是 不是 寻找随处可见的正式定义(例如 here 和 here——我可以和其他任何人一样使用 google)，甚至是任何形式的正式定义。相反，我希望找到的是简洁明了的解释，不会为了完整性而牺牲清晰度。

Answer 1

如果您还记得生成这些语言的自动机，也许您会更好地理解。

常规语言 由常规自动机生成。他们对过去只有有限的了解(他们的计算内存有限制)，所以每次你有一种后缀取决于前缀的语言(回文语言)时，这不能用常规语言来完成。

上下文无关语言 由非确定性下推自动机生成。他们对过去有一种了解(堆栈，与常规自动机相比不受限制)，但堆栈只能从顶部查看，因此您对过去没有完整的了解。

上下文相关语言 由线性绑定(bind)的非确定性图灵机生成。他们知道过去并且可以处理不同的上下文，因为它们是非确定性的，并且可以随时访问所有过去。

不受限制的语言 由图灵机生成。根据 Church-Turing-Thesis，图灵机能够计算出你能想象到的一切(这意味着一切都是可判定的)。