賈卡，J.M.

[拼音]：xingshi yuyan lilun

[英文]：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可以被ω 所替換。因此，一型文法和一型語言又分別叫上下文有關文法和上下文有關語言。

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左商(L2L1=｛Q│PQ∈L1，P∈L2｝)、右商(L1/L2)等。早在1961年即有人指出：一個上下文無關語言和一個正則語言之交仍是上下文無關語言。不久人們發現，這一結果具有相當的普遍性：幾乎所有重要的語言族都具有在與正則語言相交下封閉的性質。從60年代中期開始，研究某些語言族在某些代數運算下的封閉性已經成為形式語言代數研究的一箇中心課題。它不但表明許多已知的重要語言族具有優美的封閉性質，而且還是生成新的語言族的有力工具。在這方面，最重要的成果之一就是金斯堡等人在1966年提出的抽象語言族(AFL)思想。

喬姆斯基分層的四型語言在一些代數運算下的封閉性如表1所列。

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

喬姆斯基的變換文法概念在許多方面得到了推廣，從而也增強了描述形式語言的能力。比較重要的有下列兩個方向。

（1）對於每一步變換時允許使用的產生式加以限制。例如，矩陣文法把產生式分成有限多個有序組，它要求每一步變換必須連續地使用整組產生式。時控文法也把產生式分組，規定每一時刻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系統生成的語言。

（2）喬姆斯基文法生成的物件都是由字母表∑中的符號組成的符號串，因此又稱為串文法。如果對∑中的元素的型別加以擴充，允許它們是樹，則成為樹文法。允許元素為圖，就有了圖文法。它們統稱為高維文法，也有人研究更復雜的高維文法。