形式语言理论（formal language theory）是用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的产生方式、一般性质和规则的理论。形式语言是模拟这些语言的一类数学语言，它采用数学符号，按照严格的语法规则构成。从广义上说，形式语言是符号取自某个字母表的字符串的集合。

简介

形式文法

同形式文法

形式语言谱系

历史情况

形式语言与自然语言的区别

变换文法描述

其他信息

变换文法概念

简介

如同自然语言具有语法规则一样，形式语言也是由形式文法生成的。一个形式文法是一个有穷变元集合，这些变元也称为非终结符或语法范畴。每个变元都可以用来定义语言，定义方式可以是递归的，即通过一些称为终结符的原始符号，加上变元自身，递归地加以定义。和变元有关的规则称为生成式，生成式决定了语言是如何构造出来的。一个典型的生成式表示：给定变元所代表的语言包含这样一些字符串，它们是通过连结运算，将另外某些变元语言中的字符串和若干终结符连结起来而得到的。

形式文法

形式文法被严格地定义为四元组G=（V，T，P，S），其中V和T分别是变元和终结符的有穷集合，并且V和T没有公共元素，即V∩T=Æ。S是一个特殊变元，称为开始符号。P是生成式的有穷集合，生成式的基本形式是：a→β，这里a和β，这里a和β都是（V∪T）*中的元素，即它们都是由变元和终结符组成的符号串，但要求a至少含有一个非终结符。在形式文法定义中，生成式集合P是至关重要的。在对使用符号的惯例作某些约定后，仅仅考查生成式，就能推断出一个文法的变元、终结符和开始符号，故可以友爱过列出生成式来定义一个形式文法。

同形式文法

同形式文法G=（V，T，P，S）产生的形式语言记为L（G）。L（G）中的字符串ω都具有如下特点：①该字符串仅由终结符组成，即ω∈T*；②该字符串能由开始符号S派生出来，即从S出发，通过应用零个或多个P中的生成式，由S可以推导出ω。

形式语言谱系

根据P中生成式a→β的特点，可以将形式文法及其产生的形式语言分类，构成所谓的形式语言谱系。形式语言理论中重点研究四类文法和语言：①0型文法。又称为无限制文法。这种文法对生成式a→β不作特殊限制，a和β可以是任意的文法符号串，当然a不能是空字符串。0型文法是形式语言谱系中最大的文法类。由0型文法产生的形式语言恰是图灵机所识别的语言类，即递归可枚举语言。②1型文法。又称为上下文有关文法。这种文法要求生成式a→β满足|a|≤|β|，即β要至少和a一样长。由1型文法产生的语言称为1型语言或上下文有关语言。1型语言恰是非确定型线性有界自动机所识别的语言类。③2型文法。又称为上下文无关文法。这种文法要求生成式a→β中的a必须是变元。由2型文法产生的语言称为2型语言或上下文无关语言。2型语言恰是由下推自动机所识别的语言类。④3型文法。又称为正则文法。这种文法分为两种类型：第一类要求生成式的形式必须是A→ωB或A→ω，其中A，B都是变元，ω是终结符串（可以是空串），这种特殊的正则文法称为右线性文法。第二类正则文法称为左线性文法，它要求生成式必须是A→Bω，或A→ω的形式。由正则文法生成的语言称为正则语言，它恰是有穷自动机所识别的语言类。

上述定义的4种语言类具有依次包含关系，即对于i=0，1，2，在不考虑空字符串时，i型语言都真包含i+1型语言。

历史情况

形式语言的研究始于20世纪初，把形式语言用于模拟自然语言是50年代中期的事。当时，许多数理语言学家致力于用数学方法研究自然语言的结构，尤其是1946年电子计算机出现以后，人们很快想到用计算机来作自然语言的机械翻译。可是这项工作在取得一些初步的成功以后便停滞不前，翻译的质量很难提高，主要是因为当时对自然语言结构的理解太表面化。1956年，N.乔姆斯基发表了用形式语言方法研究自然语言的第一篇文章。他对语言的定义方法是：给定一组符号（一般是有限多个），称为字母表，以∑表之。又以∑*表示由∑中字母组成的所有符号串（或称字，也包括空字）的集合。则∑*的每个子集都是∑上的一个语言。例如，若令∑为26个拉丁字母加上空格和标点符号，则每个英语句子都是∑*中的一个元素，所有合法的英语句子的集合是∑*的一个子集，它构成一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来。　1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为 BNF范式的形式方法来描述程序设计语言的语法。不久，人们即发现BNF范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。

形式语言与自然语言的区别

形式语言与自然语言有两个重要的区别。形式语言的界限是明确的，而自然语言的界限往往不明确。因为自然语言有许多方言和习惯用法，而且处于不断发展之中。其次，自然语言不管如何庞大，它总是有限的。形式语言则以无限的语言为主要研究对象。例如，所有由n个ɑ构成的字（n≥1）组成一个语言Lɑ={ɑ，ɑɑ，ɑɑɑ，…},它就是无限的。因此，研究形式语言遇到的第一问题就是描述问题。描述的手段必须是严格的，而且必须能以有限的手段描述无限的语言。

变换文法描述

乔姆斯基用变换文法作为形式语言的描述手段。例如，语言Lɑ可用如下的变换文法描述:{S→ɑ,S→ɑS}。这个文法由两条变换规则组成。每一步变换（也叫推导）都用一条变换规则的右部替换它的左部。S是出发点，代表Lɑ中任何一个可能的句子。例如，句子ɑɑɑɑɑ可以这样推导出来：S→ɑS→ɑɑS→ɑɑɑS→ɑɑɑɑS→ɑɑɑɑɑ。推导共分五步。前四步用了第二条规则，第五步用了第一条规则。按这个办法，可以生成Lɑ中的所有句子，即整个Lɑ语言。

严格地说，变换文法定义成四元组G=（∑，V，S，P）。∑是字母表，又称终结符号表。V 是变量表，又称非终结符号表，S是出发符号，P是变换规则（又称产生式）的集合，其中∑，V和P 都是有限集，∑∩V=φ,S∈V。又令α和β分别表示（∑∪V)+和 （∑∪V)*中的元素（用+代替*表示不含空字），则P 中所有的产生式皆形如 α→β，表示用β替换α。这样定义的文法称为零型文法，又称短语结构文法。由零型文法生成的语言称零型语言。每个零型语言都是递归可枚举集（见可计算性理论），反之亦然。

以|α|表示符号串α的长度。对零型文法的所有产生式加限制|α|≤|β|，即得到一型文法。由一型文法生成的语言称一型语言。一型文法也可以这样定义：它的所有产生式均取γAδ→γωδ的形式，其中γ，ω，δ∈（V∪∑）*,|ω|>0,A∈V。其直观意义是：在左有γ，右有δ的环境下，A可以被ω 所替换。因此，一型文法和一型语言又分别叫上下文有关文法和上下文有关语言。

如果要求一型文法中α∈V，便得到二型文法，也称上下文无关文法，它生成的语言称二型语言或上下文无关语言。

其他信息

若要求二型文法中产生式的右端为ɑB或ɑ，其中ɑ∈∑，B∈V，则得到三型文法，或称正则文法，又称右线性文法，由此生成的语言称为三型语言，或正则语言，或右线性语言。

以G0,G1，G2，G3分别代表上述四类文法（有人允许二型文法的产生式中β为空），以L 0,L 1,L 2,L 3分别代表四类语言，又以L r表示由递归集构成的语言类，则有L 3嶅L 2嶅L 1嶅L r嶅L 0，这些包含都是真包含。例如，

为任意一个由第i台图灵机接受的语句}是零型语言而不是递归集

为任意一个不能由第i个一型方法产生的语句}是递归集而不是一型语言。L1={ɑnbncn|n≥1}是一型而非二型语言L2={ɑnbn|n≥1}是二型而非三型语言。L3={ɑn|n≥1}是三型语言，这里ɑn表示n个ɑ的连接。　形式语言和自动机 上述文法和语言分层方法，是乔姆斯基于1959年提出来的，因而称为乔姆斯基分层。这种分层法提出不久，人们即发现它和自动机的分类有密切的关系。到1964年，四类文法及其语言全部在自动机中找到了它们所对应的语言。零型、 一型、 二型和三型语言正好分别是图灵机、非确定型线性有界自动机、非确定型下推自动机和有限自动机接受的语言。确定型和非确定型图灵机接受的语言是相同的，确定型和非确定型有限自动机接受的语言也是相同的，因此可不加区分。确定型下推自动机接受的语言集合是非确定型下推自动机接受的语言集合的真子集，称为确定型上下文无关语言。至于非确定型线性界限自动机和确定型线性界限自动机接受的语言集合是否相同，这是一个著名的尚未解决的问题，简称LBA问题。　形式语言的代数性质 研究形式语言的第三种途径是把它作为一种代数结构来考察。可以施行于语言的代数运算包括求交（L1∩L2）、求并（L1L2）、求差（L1-L2）、求补（～L，即∑*-L）、反演（L-1，ɑb∈L凮bɑ∈L-1）、乘积（L1·L2,W1∈L1,W2∈L2→W1W2∈L1·L2）、乘幂闭包（L*，W ∈L→∈L*,n≥0）、无空字乘幂闭包（L*减去空字ε）、同态（L1→L2）、无空字同态、置换【（b(L）、L 中每个字母置换成一个语言、字母串置换成与串中各字母对应之语言的乘积）】、正则置换（置换语言都是正则语言）、L1对L2左商（L2\\L1={Q│PQ∈L1,P∈L2})、右商（L1/L2）等。早在1961年即有人指出：一个上下文无关语言和一个正则语言之交仍是上下文无关语言。不久人们发现，这一结果具有相当的普遍性：几乎所有重要的语言族都具有在与正则语言相交下封闭的性质。从60年代中期开始，研究某些语言族在某些代数运算下的封闭性已经成为形式语言代数研究的一个中心课题。它不但表明许多已知的重要语言族具有优美的封闭性质，而且还是生成新的语言族的有力工具。在这方面，最重要的成果之一就是金斯堡等人在1966年提出的抽象语言族(AFL）思想。

乔姆斯基分层的四型语言在一些代数运算下的封闭性如表1所列。

表2

形式语言的研究涉及许多判定问题，一些已有的成果如表2。表中D表示可判定；U表示不可判定；G表示文法，L表示语言。

变换文法概念

乔姆斯基的变换文法概念在许多方面得到了推广，从而也增强了描述形式语言的能力。比较重要的有下列两个方向。

①对于每一步变换时允许使用的产生式加以限制。例如，矩阵文法把产生式分成有限多个有序组，它要求每一步变换必须连续地使用整组产生式。时控文法也把产生式分组，规定每一时刻t只能从第t组中选一产生式加以应用。有序文法把产生式排成偏序，只有当排在前面的产生式不能应用时，才允许使用排在后面的产生式。在这一类推广中，研究得最多的还是L系统。这是于 1968年提出的，背景是用细胞自动机构造生物发育进程的模型。它规定在每一步变换中，对同样的左部符号必须使用同一个产生式。例如若B→α和B→β同为产生式，则从BAB只能推出αAα和βAβ，而不能推出αAβ或βAα。L系统的出发符号是一个字母串，一般没有终结符和非终结符之分。在名称上，它用O表示零面（产生式上下文无关），I表示上下文有关，D表示决定型，P表示增殖型（任何产生式不产生空字），T表示产生式按表格分组，以这些区别来划分L系统的子系统。例如，DTOL语言表示由决定型、零面、表格型L系统生成的语言。

②乔姆斯基文法生成的对象都是由字母表∑中的符号组成的符号串，因此又称为串文法。如果对∑中的元素的类型加以扩充，允许它们是树，则成为树文法。允许元素为图，就有了图文法。它们统称为高维文法，也有人研究更复杂的高维文法。