形式語言理論

形式語言理論是用數學方法研究自然語言(如英語)和人工語言(如程式設計語言)的語法的理論。它只研究語言的組成規則，不研究語言的含義。形式語言理論在自然語言的理解和翻譯、計算機語言的描述和編譯、社會和自然現象的模擬、語法制導的模式識別等方面有廣泛的套用。形式語言的研究始於20世紀初，50年代中期將形式語言用於描述自然語言。

基本介紹

• 中文名：形式語言理論
• 外文名：formal language theory
• 起始時間：20世紀初

歷史發展

形式語言的研究始於20世紀初，把形式語言用於模擬自然語言是50年代中期的事。當時，許多數理語言學家致力於用數學方法研究自然語言的結構，尤其是1946年電子計算機出現以後，人們很快想到用計算機來作自然語言的機械翻譯。可是這項工作在取得一些初步的成功以後便停滯不前，翻譯的質量很難提高，主要是因為當時對自然語言結構的理解太表面化。1956年，N.喬姆斯基發表了用形式語言方法研究自然語言的第一篇文章。他對語言的定義方法是：給定一組符號（一般是有限多個），稱為字母表，以∑表之。又以∑*表示由∑中字母組成的所有符號串（或稱字，也包括空字）的集合。則∑*的每個子集都是∑上的一個語言。例如，若令∑為26個拉丁字母加上空格和標點符號，則每個英語句子都是∑*中的一個元素，所有合法的英語句子的集合是∑*的一個子集，它構成一個語言。喬姆斯基的語言定義方法為人們所公認，一直沿用下來。

1960年，算法語言ALGOL60報告發表。1961年，又發表了ALGOL60報告發表．其中第一次使用一種稱為巴克斯範式的方法來描述程式設計語言的語法。不久，人們即發現巴克斯範式系統極其類似於形式語言理論中的上下文無關文法．從而打開了形式語言廣泛套用於描述程式設計語言的局面，使它發展成為理論計算機科學的一個重要分支。

形式文法

形式文法被嚴格地定義為四元組G=（V，T，P，S），其中V和T分別是變元和終結符的有窮集合，並且V和T沒有公共元素，即V∩T=Æ。S是一個特殊變元，稱為開始符號。P是生成式的有窮集合，生成式的基本形式是：a→β，這裡a和β，這裡a和β都是（V∪T）*中的元素，即它們都是由變元和終結符組成的符號串，但要求a至少含有一個非終結符。在形式文法定義中，生成式集合P是至關重要的。在對使用符號的慣例作某些約定後，僅僅考查生成式，就能推斷出一個文法的變元、終結符和開始符號，故可以友愛過列出生成式來定義一個形式文法。

形式語言譜系

根據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型語言。

變換文法描述

喬姆斯基用變換文法作為形式語言的描述手段。例如，語言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，便得到二型文法，也稱上下文無關文法，它生成的語言稱二型語言或上下文無關語言。

特點

形式語言與自然語言有兩個重要的區別。形式語言的界限是明確的，而自然語言的界限往往不明確。因為自然語言有許多方言和習慣用法，而且處於不斷發展之中。其次，自然語言不管如何龐大，它總是有限的。形式語言則以無限的語言為主要研究對象。例如，所有由n個ɑ構成的字（n≥1）組成一個語言Lɑ={ɑ，ɑɑ，ɑɑɑ，…},它就是無限的。因此，研究形式語言遇到的第一問題就是描述問題。描述的手段必須是嚴格的，而且必須能以有限的手段描述無限的語言。