山東抗日民主根據地

[拼音]：Xingshi Wenfa

數理語言學用於生成語言的文法。形式文法是數目有限的規則的集合，這些規則可生成語言中的合格句子，並排除語言中的不合格句子。形式文法符號為 G，文法所生成的語言符號為L(G)。

定義

美國語言學家N.喬姆斯基把形式文法 G定義為四個專案的組合：

G=(VN，VT，S，P)

其中，VN是非終極符號，不能處於生成過程的終點；VT是終極符號，能處於生成過程的終點；VN與VT不相交，沒有公共元素； S是VN中的初始符號； P是重寫規則，其一般形式為：

嗞→ψ

這裡，嗞和ψ都是符號串。

如果用符號＃來表示符號串中的界限，那麼，可以從初始符號串＃S＃開始，應用重寫規則＃S＃→＃嗞1＃，從＃ S＃構成新的符號串＃嗞1＃，再利用重寫規則＃嗞1＃→＃嗞2＃，從＃嗞1＃構成新的符號串＃嗞2＃，……一直到得出不能再繼續重寫的符號串＃嗞n＃為止，這樣得出的終極符號串＃嗞n＃，顯然就是語言L(G)中合格的句子。

例如，在英語中，有如下的文法：

G=(VN，VT，S，P)

VN={NP，VP，T，N，V}

VT ={the，man，boy，ball，saw，hit，took，…}

S=S

P:S →NP⌒VP①

NP→ T⌒N ②

VP→ V⌒NP③

T →the ④

N →{man，boy，ball，…}⑤

V→{saw，hit，took，…} ⑥這裡，初始符號S表示句子，NP表示名詞短語，VP表示動詞短語， T表示指示詞， N表示名詞，V表示動詞。利用這些重寫規則，可以從初始符號S開始，生成英語的句子“The man saw the ball”，“The man took the ball”，“The boy hit the ball”，等等。

“The man saw the ball”的生成過程可寫成如下形式，後面註明所用重寫規則的號碼：

S

NP⌒VP ①

T⌒N⌒VP ②

T⌒N⌒V⌒NP③

the N⌒V⌒NP ④

the man V⌒NP ⑤

the man saw NP⑥

the man saw T⌒N②

the man saw the N ④

the man saw the ball⑤

這樣寫出來的生成過程，叫做推導史。

分類

喬姆斯基根據重寫規則的形式，把形式文法分為 4類：

（1）O型文法：重寫規則為嗞→ψ，並且要求嗞不是空符號串。

（2）上下文敏感文法:重寫規則為嗞1A嗞2→嗞1ω嗞2。在上下文嗞1→嗞2中，單個的非終極符號 A被重寫為符號串ω，所以，這種文法是上下文敏感的。

（3）上下文自由文法：重寫規則為A→ω。當A重寫為ω時，沒有上下文的限制，所以，這種文法是上下文自由的。

（4）有限狀態文法：重寫規則為 A→aQ或A→a。其中，A和Q是非終極符號，a是終極符號，而A→a只不過是A→aQ當 Q為空符號時的一種特殊情況。如果把A和Q看成不同的狀態，那麼，由重寫規則可知，由狀態 A轉入狀態Q時，可生成一個終極終號a，因此，這種文法叫做有限狀態文法。

各種形式文法的關係

每一個有限狀態文法上下文都是自由的，每一個上下文自由的文法上下文都是敏感的，每一個上下文敏感的文法都是 O型的。喬姆斯基把由O型文法生成的語言叫O型語言，把由上下文敏感文法、上下文自由文法、有限狀態文法生成的語言分別叫做上下文敏感語言、上下文自由語言、有限狀態語言。有限狀態語言包含於上下文自由語言中，上下文自由語言包含於上下文敏感語言中，上下文敏感語言包含於 O型語言中。

形式文法的理論是當代電腦科學的基礎理論之一，在演算法分析、編譯技術、影象識別、人工智慧等領域中得到廣泛的應用。

參考書目

N.Chomsky，Three models for the description oflɑnɡuɑɡe ， 《 IRETransactionofinformation Theory》.Vol.1，No.3，pp.113～124，1956.