我正在尝试找到乔姆斯基提出的形式语法的4个层次(无限制，上下文相关，上下文无关，常规)的简单解释(即非形式化)。
自从我学习形式语法以来，这已经是一个时代了，各种定义现在让我难以理解。明确地说，我是，而不是，而是在您随处可以找到的正式定义(例如here和here-我可以在Google上以及其他任何人使用谷歌搜索)，或者甚至是任何形式的正式定义。相反，我希望找到的是简洁明了的解释，为了完整起见，它们并没有牺牲清晰性。
最佳答案
如果您还记得生成这些语言的自动机，也许您会更好地理解。
常规语言由常规自动机生成。他们只对过去有一定的了解(他们的计算内存有限制)，因此，每当您有一种后缀取决于前缀的语言(回文语言)时，常规语言就无法做到。
上下文无关的语言由不确定的下推自动机生成。他们对过去有一定的了解(堆栈，与常规自动机相比没有限制)，但是只能从顶部查看堆栈，因此您没有对过去的完整了解。
上下文相关语言是由线性绑定(bind)的不确定性图腾机生成的。他们了解过去并可以处理不同的上下文，因为它们不确定，可以随时访问所有过去。
非限制语言由图灵机生成。根据Church-Turing-Thesis的介绍，图灵机可以计算出您可以想象的一切(这意味着可以决定的一切)。
关于grammar - 普通英语的乔姆斯基阶层，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8398030/