chomsky层次结构用简单的英语

Question

我试图找到一个简单的(即非正式的)解释,正如乔姆斯基所阐述的4级正式语法(无限制,上下文敏感,无上下文,常规).

自从我学习正式语法以来,这已经是一个时代了,各种各样的定义现在让我难以想象.要明确的是,我不是在寻找你​​到处都可以找到的正式定义(例如这里和这里 - 我可以谷歌以及其他任何人),或者甚至是任何形式的正式定义.相反,我希望找到的是干净简单的解释,为了完整性而不牺牲清晰度.

Answer 1

如果你还记得生成这些语言的自动机,也许你会更好地理解.

常规语言由常规自动机生成.他们只掌握过去的知识(计算内存有限制)所以每当你有一个带有后缀的语言,这取决于前缀(回文语言),这是常规语言无法做到的.

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

上下文相关语言由线性绑定的非确定性图灵机生成.他们了解过去并且可以处理不同的背景,因为它们是非确定性的,并且可以随时访问所有过去.

图灵机生成无限制语言.根据Church-Turing-Thesis,图灵机能够计算出你能想象到的一切(这意味着一切都是可判断的).