正文
形式語言理論在自然語言的理解和翻譯、計算機語言的描述和編譯、社會和自然現象的模擬、語法制導的模式識別等方面有廣泛的套用。歷史情況 形式語言的研究始於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＝｛ɑn bn cn |n≥1｝是一型而非二型語言L2=｛ɑn bn |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所列。
形式語言理論
形式語言理論①對於每一步變換時允許使用的產生式加以限制。例如,矩陣文法把產生式分成有限多個有序組,它要求每一步變換必須連續地使用整組產生式。時控文法也把產生式分組，規定每一時刻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系統生成的語言。
②喬姆斯基文法生成的對象都是由字母表∑中的符號組成的符號串，因此又稱為串文法。如果對∑中的元素的類型加以擴充，允許它們是樹，則成為樹文法。允許元素為圖，就有了圖文法。它們統稱為高維文法，也有人研究更複雜的高維文法。
