我试图找到乔姆斯基提出的 4 个级别的正式语法（无限制、上下文相关、上下文无关、常规）的简单（即非形式）解释。
我已经很久没有学习正式语法了，各种定义现在让我难以想象。明确地说，我是not寻找随处可见的正式定义（例如here http://en.wikipedia.org/wiki/Chomsky_hierarchy and here http://en.wikibooks.org/wiki/Computability_and_Complexity/Formal_Languages/Chomsky_Hierarchy——我可以像其他人一样用谷歌搜索），或者甚至是任何形式的正式定义。相反，我希望找到的是干净简单的解释，不会为了完整性而牺牲清晰度。
如果您还记得生成这些语言的自动机，也许您会更好地理解。
常规语言由常规自动机生成。他们对过去只有有限的知识（他们的计算内存有限制），所以每当你有一种后缀取决于前缀（回文语言）的语言时，这不能用常规语言来完成。
上下文无关语言由非确定性下推自动机生成。他们对过去有一定的了解（堆栈，与常规自动机相比不受限制），但堆栈只能从顶部查看，因此您对过去没有完整的了解。
上下文相关语言由线性绑定的非确定性图灵机生成。他们了解过去并且可以处理不同的情况，因为他们是不确定的并且可以随时访问所有过去的情况。
语言不受限制由图灵机生成。根据丘奇图灵论文，图灵机能够计算你能想象的一切（这意味着一切可判定的）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
