我试图找到乔姆斯基提出的 4 级形式语法（无限制、上下文相关、上下文无关、常规）的简单（即非形式）解释。
自从我学习形式语法以来已经过去了一个时代，现在各种定义让我难以想象。需要明确的是，我不是在寻找随处可见的正式定义（例如这里和这里——我可以和其他任何人一样使用谷歌搜索），甚至不是任何形式的正式定义。相反，我希望找到的是简洁明了的解释，不会为了完整性而牺牲清晰度。
问问题
7475 次
3 回答
19
如果您还记得生成这些语言的自动机，也许您会更好地理解。
正则语言是由正则自动机生成的。他们对过去只有有限的了解（他们的计算内存有限制），所以每次你有一种后缀取决于前缀的语言（回文语言）时，这不能用常规语言来完成。
上下文无关语言由非确定性下推自动机生成。他们对过去有一种了解（堆栈，与常规自动机相比不受限制），但堆栈只能从顶部查看，因此您对过去没有完整的了解。
上下文相关语言是由线性绑定的非确定性图灵机生成的。他们知道过去并且可以处理不同的上下文，因为它们是非确定性的，并且可以随时访问所有过去。
不受限制的语言是由图灵机生成的。根据 Church-Turing-Thesis，图灵机能够计算出你能想象到的一切（这意味着一切都是可判定的）。
于 2011-12-06T10:13:50.160 回答
2
对于常规语言，有许多等价的表征。它们提供了许多不同的方式来看待常规语言。很难给出“简单的英语”定义，如果您发现很难理解常规语言的任何特征，那么“简单的英语”解释不太可能有帮助。从定义和各种闭包属性中要注意的一件事是，常规语言以某种方式体现了“有限性”的概念。但是，如果不更好地熟悉常规语言，这又是很难理解的。
你觉得有限自动机的概念不简单和干净吗？
让我提一些许多等价的特征（至少对于其他读者来说）：
于 2011-12-06T15:37:10.933 回答
2
常规：这些语言用有限自动机回答是/否
上下文无关：这些语言在给定输入词时（使用状态机和堆栈），如果它是该语言的成员，我们总是可以回答是/否
上下文相关：只要语法中的产生永远不会缩小（ α -> β ），我们可以回答是/否（使用状态机和与输入呈线性大小的内存块）
递归可枚举：它可以回答是，但如果不是，它将进入无限循环
请参阅此视频以获取完整说明。
于 2014-07-06T02:39:28.167 回答