形式语言理论(卷名：电子学与计算机)
formal language theory
用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的语法的理论。形式语言就是模拟这些语言的数学工具。它只研究语言的组成规则，不研究语言的含义。
形式语言理论在自然语言的理解和翻译、计算机语言的描述和编译、社会和自然现象的模拟、语法制导的模式识别等方面有广泛的应用。
历史情况 形式语言的研究始于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)、求并(L1
L2)、求差(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。表中D表示可判定；U表示不可判定；G表示文法，L表示语言。
乔姆斯基的变换文法概念在许多方面得到了推广，从而也增强了描述形式语言的能力。比较重要的有下列两个方向。
①对于每一步变换时允许使用的产生式加以限制。例如，矩阵文法把产生式分成有限多个有序组，它要求每一步变换必须连续地使用整组产生式。时控文法也把产生式分组，规定每一时刻t只能从第t组中选一产生式加以应用。以嫓(t)表示第t组产生式，则当有t0使嫓(t+t0)＝嫓(t)时，它称为周期时控文法。有序文法把产生式排成偏序，只有当排在前面的产生式不能应用时，才允许使用排在后面的产生式。在这一类推广中，研究得最多的还是L系统。这是于 1968年提出的，背景是用细胞自动机构造生物发育进程的模型。它规定在每一步变换中，对同样的左部符号必须使用同一个产生式。例如若B→α和B→β同为产生式，则从BAB只能推出αAα和βAβ，而不能推出αAβ或βAα。L系统的出发符号是一个字母串，一般没有终结符和非终结符之分。在名称上，它用O表示零面（产生式上下文无关），I表示上下文有关，D表示决定型，P表示增殖型（任何产生式不产生空字），T表示产生式按表格分组，以这些区别来划分L系统的子系统。例如，DTOL语言表示由决定型、零面、表格型L系统生成的语言。
②乔姆斯基文法生成的对象都是由字母表∑中的符号组成的符号串，因此又称为串文法。如果对∑中的元素的类型加以扩充，允许它们是树，则成为树文法。允许元素为图，就有了图文法。它们统称为高维文法，也有人研究更复杂的高维文法。