补充资料：乔姆斯基层次

乔姆斯基层次
Chomsky hierarchy

　　关于语言的描述，除了从生成的角度，即文法的角度之外，还可从识别的角度，即自动机的角度来描述。相应于四类文法有四类自动机，即图灵机、线性有界自动机、下推自动机和有限自动机。并证明了:图灵机识别的语言类恰为易;线性有界自动机识别的语言类恰为砚;下推自动机识别的语言类恰为魏;有限自动机识别的语言类恰为马。有限状态自动机和正则文法的等价性是由N.CI功lsky和G.A.肠Uer给出的，N.Ch以nsky和J，Evey证明了下推自动机和上下文无关文法的等价性。5.Y.Kur浏a证明了线性有界自动机与上下文有关文法的等价性。N.Chon玲ky证明了图灵机与短语结构文法的等价性。Q iuomusi!一eengei乔姆斯基层次(ch0Insky hiera代hy)由N.Cllomsky提出的形式语言的分层(参见形式语言理论)。它研究四类文法，即短语结构文法、上下文有关文法、上下文无关文法和正则文法之间存在的层次关系，以及由该四类文法产生的语言族所形成的层次。 短语结构文法一个四元组G=(乞，v，S，尸)，其中V是非终结符的有穷字母表，乏是终结符的有限字母表，尸是生成式的有限非空集，尸中的生成式均为a~月的形式，。任(乞UV)十，夕〔(乏UV)‘，S(任V)称为开始符号。短语结构文法是一种非受限文法，也称为0型文法和半丘系统。对短语结构文法中的生成式作某些限制，即得到上下文有关文法、上下文无关文法和正则文法。 上下文有关文法一种特殊的短语结构文法，也称为1型文法。它限制尸中的生成式均为alAaZ~a1角2的形式，其中A任v，。1，aZ，口e(艺Uv)‘渭举。。对这类文法，在派生中只有“上下文”a;，a2分别出现在A的左、右邻近时，才允许用召替换A，故云“上下文有关”。 上下文无关文法一类特殊的上下文有关文法，也称为2型文法。它限制尸中的生成式均为A~夕的形式，其中A〔V，月e(乞UV)‘，召共。。 正则文法一类特殊的上下文无关文法，也称为3型文法。这类文法要求尸中的生成式均为A一aB或A一a的形式，其中A，BeV，a〔乞。在有些文献中也称左线性文法或右线性文法为正则文法。它们都是和正则文法等价的。称文法是左(右)线性文法，如果尸中的生成式都是A~召t更(A~仪汪3)或A~二的形式，其中A，B任V，、任刃’。 由i型文法G=(刃，V，S，尸)产生的语言称为i型语言，i=0，1，2，3，记作L(G)，即L(G)=!x〔乞’!S=翔￡ G 从四类文法的定义可见，它们之间存在明显的层次关系，从而，四个语言类也存在层次关系。若令才表示。型语言类，。二O，1，2，3，则马互摊二溉g易。由于L=}砂护}n)1}任摊，但不是3型语言，故妈是摊的真子集;又由于L=laz‘】i)1}任玛，但不是2型语言，所以绳是找的真子集。类似地，在易中也存在不属于哭的语言，故哭也是易的真子集。这就是所谓的乔姆斯基层次。在有些文献中也称为乔姆斯基分层或乔姆斯基谱系。
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。