普通英语的乔姆斯基阶层 [英] chomsky hierarchy in plain english

问题描述

我试图找到乔姆斯基提出的形式语法的四个层次（无限制，上下文相关，上下文无关，常规）的简单（即非正式）解释。

I'm trying to find a plain (i.e. non-formal) explanation of the 4 levels of formal grammars (unrestricted, context-sensitive, context-free, regular) as set out by Chomsky.

自从我学习形式语法以来已经有一个时代了，各种定义现在让我难以理解。需要明确的是，我不正在寻找随处可见的正式定义（例如，此处和此处-我可以在Google以及其他任何人身上使用Google，甚至可以是任何形式。取而代之的是，我希望找到的是简洁明了的解释，它们并没有为了完整性而牺牲清晰度。

It's been an age since I studied formal grammars, and the various definitions are now confusing for me to visualize. To be clear, I'm not looking for the formal definitions you'll find everywhere (e.g. here and here -- I can google as well as anyone else), or really even formal definitions of any sort. Instead, what I was hoping to find was clean and simple explanations that don't sacrifice clarity for the sake of completeness.

推荐答案

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

Maybe you get a better understanding if you remember the automata generating these languages.

常规语言是由常规自动机生成的。他们对过去只有很少的了解（它们的计算内存有限制），因此，每当您有一种后缀取决于前缀的语言（回文语言）时，常规语言就无法做到这一点。

Regular languages are generated by regular automata. They have only have a finit knowledge of the past (their compute memory has limits) so everytime you have a language with suffixes depending on prefixes (palindrome language) this can not be done with regular languages.

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

Context-free languages are generated by nondeterministic pushdown automata. They have a kind of knowledge of the past (the stack, which is not limited in contrast to regular automata) but a stack can only be viewed from top so you don't have complete knowledge of the past.

上下文相关语言是由线性绑定的不确定性图腾机生成的。他们了解过去并且可以处理不同的上下文，因为它们不确定，可以每次访问所有过去。

Context-sensitive languages are generated by linear-bound non-deterministic turing machines. They know the past and can deal with different contexts because they are non-deterministic and can access all the past at every time.

不受限制的语言由图灵机生成。根据Church-Turing-Thesis的介绍，图灵机可以计算出您可以想象的一切（这意味着可以决定的一切）。

Unrestricted languages are generated by Turing machines. According to the Church-Turing-Thesis turing machines are able to calculate everything you can imagine (which means everything decidable).

这篇关于普通英语的乔姆斯基阶层的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！