http://s5/middle/72d083c7g9ec980da6674&690

                                          Chomsky层级  

                  语法的Chomsky层级

                                           冯志伟

    把句子分割为成分层次的思想最早出现于实验心理学的奠基人W. Wundt（温特）的《大众心理学》（Voelkerpsychologie，1900）一书中。 与此相反，从古典时期开始的传统的欧洲语法研究如何确定具体的单词之间的关系，而不是研究确定单词所表示的成分之间的层次关系。

    Wundt关于组成性的思想被Leonard Bloomfield（布龙菲尔德）在他于1914年出版的早期著作《语言研究导论》（An Introduction to the Study of Language）中引入了语言学。1933年在他的著作《语言论》（Language）发表的时候，“直接成分分析法”（immediate-constituent analysis）已经成为了美国语言学研究中的相当完善的方法。与此相反，欧洲的句法学家们仍然强调以词为基础的语法或者依存语法（dependency grammar）。以成分为基础的语法和以词为基础的语法各有千秋，在自然语言处理中，它们形成了两种有代表性的形式模型。我们在这里首先讨论以成分为基础的形式模型（如“短语结构语法”），以后我们还要讨论以词为基础的形式模型（如“依存语法”）。

                           http://s14/middle/72d083c7g9ec99857ef6d&690

                                 Leonard Bloomfield

       美国结构主义提出了关于直接成分的一些定义，把他们的研究说成是“发现程序”（discovery procedure）；这是描写语言句法的一种有方法论色彩的算法。总起来说，这些研究都试图印证“直接成分的首要标准就是一个组合作为简单的单位起作用的程度”这样的直觉[1]（Bazell, 1952）。其中最有名的定义是Z. Harris（海里斯）关于使用“可替换性”（substitutability）试验来检验单独的单位“分布相似性”（distributional similarity）的思想。从实质上说，这种方法是把一个结构分解为若干个成分，把它替换为可能成分的简单结构；如果可以用一个简单形式（例如，man）来替换一个比较复杂的结构（例如，intense young man），那么，这个比较复杂的结构intense young man就可能是一个成分。Harris的试验成为了把成分看成是一种等价类的这种直觉的开端。

    这种层次成分思想的最早的形式化描述是美国语言学家N. Chomsky（1928- ）在1956年定义的短语结构语法，后来Chomsky又先后在1957年和1975年做了进一步的扩充，并提出反对的理由来论证。从此以后，大多数的生成语法理论都建立在短语结构语法的基础之上，至少也是部分地建立在短语结构语法的基础之上。

http://s7/middle/72d083c7g9ec9a2f57166&690

                                       N. Chomsksy

   Chomsky于1928年12月7日生于美国费城。1947年，他认识了著名语言学家Z．Harris。在学习了Harris的《结构语言学方法》一书的若干内容之后，他被Harris那种严密的方法深深地吸引了。从此，他立志以语言学作为自己毕生的事业，进了Harris执教的宾夕法尼亚大学，专攻语言学。他决定把Harris的方法作适当的改变，建立一种形式语言理论，采用递归的规则来描写句子的形式结构，从而使语法获得较强的解释力。为了完成形式语言理论这一有意义的研究课题，在Harris的建议下，Chomsky从1953年开始学习哲学、逻辑学和现代数学。1954年，Chomsky着手写《语言理论的逻辑结构》(The Logical Structure of Linguistic Theory)一书。在这部著作中，他初步勾画出生成语法的理论观点和思想方法。1955年秋，Chomsky到麻省理工学院(MIT)电子学研究室做研究工作，并在现代语言学系任教，给研究生讲授语言学、逻辑学、语言哲学等课程。Chomsky除了在美国麻省理工学院担任语言学教授之外，他还是牛津大学约翰·洛克讲座讲师、柏克莱加利福尼亚大学客座教授，并在普林斯顿进修学院和哈佛认知研究中心任高级研究员，在伦敦大学主持谢尔门纪念讲座。Chomsky是美国科学院院士、英国科学院通讯院士，并任世界裁军和平同盟的理事。芝加哥大学、芝加哥洛约拉大学、伦敦大学和北京大学都授予他名誉博土学位。

   Chomsky 在《语言描写的三个模型》(Three models for the description,1956)《句法结构》(Syntactic Structure, 1957)《有限状态语言》(Finite-state language,1958)《论语法的某些形式特性》(On certtai formal properties of grammars, 1959)《语法的形式特性》(Formal properties of grammars,1963)等论著中，建立了形式语言理论(formal language theory)的完整系统，这种理论基本上是从语言生成的角度来进行研究的。短语结构语法是形式语言理论的主要内容,是自然语言处理中最重要的形式模型。

在形式语言理论中，Chomsky提出了不同于传统语法的“形式语法”（formal grammar）的定义。因此，我们要了解短语结构语法，首先必须了解Chomsky的形式语法究竟是什么。

    Chomsky把形式语法理解为数目有限的规则的集合，这些规则可以生成语言中的合格句子，并排除语言中的不合格句子。形式语法的符号用G 表示，用语法G所生成的形式语言用L(G)表示。形式语言是一种外延极为广泛的语言，它既可以指自然语言，也可以指各种用符号构成的语言（例如，计算机使用的程序设计语言）。Chomsky把自然语言和各种符号语言放在一个统一的平面上进行研究，因而，他的理论就更加具有概括性。

     Chomsky把形式语法G定义为四元组:

               G=(Vn, Vt, S, P)

其中,Vn是非终极符号，不能处于生成过程的终点，Vt是终极符号，只能处于生成过程的终点；Vn与Vt不相交，没有公共元素；S是Vn中的初始符号；P是重写规则，其一般形式为：

                    φ→ψ

这里，φ和ψ都是符号串。

    如果用符号#来表示符号串中的界限，那么，可以从初始符号串#S#开始，应用重写规则 #S#→#φ₁#,从#S#构成新的符号串#φ₁#,再利用重写规则#φ₁#→#φ₂#，从#φ₁#构成新的符号串#φ₂#，……，一直到得出不能再继续重写的符号串#φ_n#为止，这样得出的终极符号串#φ_n#，显然就是形式语言L(G)中合格的句子。

    Chomsky根据重写规则的形式，把形式语法分为4类：

    1. 0型语法(type 0 grammar)：重写规则为φ → ψ，并且要求φ不是空符号串。

    2. 上下文有关语法(context-sensitive grammae)：重写规则为 φ₁Aφ₂  → φ₁ωφ₂，在上下文φ₁-φ₂中，单个的非终极符号A被重写为符号串ω，所以，这种语法对上下文敏感，是上下文有关的。上下文有关语法又叫做1型语法。

    3. 上下文无关语法(context-free grammar)：重写规则为A → ω，当A重写为ω时，没有上下文的限制，所以，这种语法对上下文自由，是上下文无关的。上下文无关语法又叫做2型语法。把上下文无关语法应用于自然语言的形式分析中，就形成了“短语结构语法”(phrase structure grammar)

    4. 有限状态语法(finite state grammar)：重写规则为A→aQ或A→a。其中，A和Q是非终极符号，a是终极符号，而A→a只不过是A→aQ这个重写规则中当Q为空符号时的一种特殊情况。如果把A和Q看成不同的状态，那么，由重写规则可知，由状态A转入状态Q时，可生成一个终极符号a，因此，这种语法叫做有限状态语法。有限状态语法又叫做3型语法。

每一个有限状态语法的都是上下文无关的，每一个上下文无关语法都是上下文有关的，而每一个上下文有关语法都是0型的，Chomsky把由0型语法生成的语言叫0型语言，把由上下文有关语法、上下文无关语法、有限状态语法生成的语言分别叫做上下文有关语言、上下文无关语言、有限状态语言。有限状态语言包含于上下文无关语言之中，上下文无关语言包含于上下文有关语言之中，上下文有关语言包含于0型语言之中。这样就形成了语法的“Chomsky层级”（Chomsky hierarchy）。在自然语言处理中,我们最感兴趣的是上下文无关语法和上下文无关语言,它们是短语结构语法理论的主要研究对象。

            http://s10/middle/72d083c7g9ec9b64bcc19&690                                           Chomsky层级

    Chomsky认为，根据这样的形式语言理论，可以采用有限的规则来描述形式上是潜在地无限的句子，达到以简驭繁的目的。他在我国黑龙江大学出版的《Chomsky语言理论简介》一书的序言中说：“一个人的语言知识是以某种方式体现在人脑这个有限的机体之中的，因此，语言知识就是一个由某种规则和原则构成的有限系统。但是一个会说话的人却能讲出并理解他从未听到过的句子以及和我们听到的不十分相似的句子。而且，这种能力是无限的。如果不受时间和记忆力的限制，那么一个人所获得的知识系统规定了特定形式、结构和意义的句子的数目也将是无限的。不难看到这种能力在正常的人类生活中得到自由的运用。我们在日常生活中所使用和理解的句子范围是极大的，无论就其实际情况而言还是为了理论描写上的需要，我们完全有理由认为人们使用和理解的句子范围都是无限的。”[2]

   早在19世纪之初，德国杰出的语言学家和人文学者W. V. Humboldt(洪堡特，1767-1835)就观察到“语言是有限手段的无限运用”。W.V.Humboldt在《论人类语言结构的差异及其对人类精神发展的影响》（1836年单独印行）一书的第十二章“对语言方法的详细分析”中说，“语言面对着一个无限的、无边无际的领域，即一切可思维对象的总和，因此，语言必须无限地运用有限的手段，而思维力量和语言创造力量的同一性确保了语言能够做到这一点。”[3] 但是，由于当时尚未找到揭示这种理解所包含的本质内容的技术工具和方法，W.V.Humboldt的论断还是不成熟的。

                 http://s14/middle/72d083c7g9ec9acc78a8d&690

                                          W.V.Humboldt

    Chomsky发展了W.V.Humboldt的理论，并从数学上作了严格的论证，这样，我们就可以根据形式语言理论来揭示“语言是有限手段的无限运用”这个论断本质内容了。

    Chomsky的形式语言理论是当代计算机科学的基础理论之一，在算法分析、编译技术、图象识别、人工智能等领域中得到广泛的应用。在自然语言处理中，它是一种重要的语言形式模型。