我們前面說過自然語言處理的歷史线婚，說在喬姆斯基之前所有關(guān)于自然語言處理的研究都是基于經(jīng)驗主義的盆均，到了喬姆斯基后所有的研究開始變得規(guī)則話了漱逸，也就是在喬姆斯基的語法理論出現(xiàn)之后

喬姆斯基曾經(jīng)把語言定義為：按照一定規(guī)律構(gòu)成的句子和符號串的有限或無限的集合游沿。根據(jù)這個定義诀黍，無論哪一種語言都是句子和符號串的集合仗处，當然自然語言也不例外，漢語吃环、英語等所有自然語言洋幻，都是一個無限集合。構(gòu)成這些集合的是句子好唯、單詞或其他符號燥翅。我國學(xué)者吳蔚天認為，可以把語言看成一個抽象的數(shù)學(xué)系統(tǒng)替蛉。無論把語言看作集合還是數(shù)學(xué)系統(tǒng)拄氯，我們都可以用數(shù)學(xué)的方法來進行刻畫和描述

那么一般地，描述一種語言可以有三種途徑：

1.窮舉法：把語言中的所有句子都枚舉出來镣煮。顯然鄙麦，這種方法只適合句子數(shù)目有限的語言胯府。（這種方法顯然不太靠譜啊，我們所使用的語言實在是太多了）

2.文法（產(chǎn)生式系統(tǒng)）描述：語言中的每個句子用嚴格定義的規(guī)則來構(gòu)造炎咖，利用規(guī)則生成語言中合法的句子。（這個聽起來靠譜多了啊乘盼，實際上也就是我們今天要說的形式語言绸栅，用嚴格定義的規(guī)則來構(gòu)造語言）

3.自動機法：通過對輸入的句子進行合法性檢驗，區(qū)別哪些是語言中的句子蓖柔，哪些不是語言中的句子风纠。（自動機是和形式語言配合其作用的，后面我們會說到每一種形式語言對應(yīng)著一個自動機）

文法用來精確地描述語言和其結(jié)構(gòu)懒闷，自動機則是用來機械地刻畫對輸入字符串的識別過程栈幸。用文法來定義語言的優(yōu)點是：由文法給予語言中的句子以結(jié)構(gòu)，各成分之間的結(jié)構(gòu)關(guān)系清楚玩焰、明了芍锚。但是，如果要直接用這些規(guī)則來確定一個字符串是否屬于這套規(guī)則所定義的語言似乎并不十分明確默刚。而由自動機來識別一個字符串是否屬于該語言則相對簡單逃魄，但自動機很難描述語言的結(jié)構(gòu)伍俘。所以自然語言處理中的識別和分析算法，大多兼取兩者之長癌瘾，下面我們說一下形式語言的四種形式妨退，都是很嚴格同時也很簡單的規(guī)則

形式語法的定義

如果我們用重寫規(guī)則α→β的形式表示蜕企，其中嚣伐，α萍丐，β均為字符串逝变。那么，這條規(guī)則表示字符串α可以被改寫成β拱层。一個初始的字符串通過不斷地運用重寫規(guī)則宴咧，就可以得到另一個字符串。如果通過選擇多個不同的規(guī)則并以不同的順序來運用這些規(guī)則的話烙肺，就可以得到不同的新字符串

從這個嚴格的定義上來看氧卧，形式語言分為四部分沙绝，或者叫四元組，N叫做非終結(jié)符星著，非終結(jié)符的意思就是可以向后繼續(xù)演化粗悯，派生出其他字符，終結(jié)符就是到這里就不能往后面派生了邮丰，P是重寫規(guī)則铭乾，重寫規(guī)則的意思就是說非終結(jié)符和終結(jié)符都要按照這個定義好的語言規(guī)則往后面派生炕檩，最后的S就是個開始按鈕的意思

正則文法（或稱3型文法）

我們這里的大寫B(tài)往往代表非終結(jié)符捌斧，用非終結(jié)符可以往后面派生其他字符捞蚂，小寫字母往往代表終結(jié)符跷究，遇到終結(jié)符我們這個字符就終止了，所以這個正則文法就是兩條派生規(guī)則丁存，非常簡單但也非常強大的給的啊柴我，用它可以產(chǎn)品很多符號集合

上下文無關(guān)文法（對的，還有上下文有關(guān)文法）

這個文法也叫2型文法，承接3型文法啊界睁，這個重寫規(guī)則只有一個晕窑，限制更少了，舉個例子：

從定義中我們可以看出敞斋，2型文法比3型文法少了一層限制疾牲，其規(guī)則右端的格式?jīng)]有約束。也就是說焰枢，規(guī)則左部的非終結(jié)符可以被改寫成任何形式舌剂，從例子中我們也可以看的出來啊

上下文有關(guān)文法（1型文法）

為啥叫上下文有關(guān)文法霍转，從上述定義也可以看出，字符串αAβ中的A被改寫成γ時需要有上文語境α和下文語境β低滩，就是因為這個

當然，α和β可以為空字符ε监憎，如果α和β同時為空時婶溯，1型文法變成了2型文法爬虱。也就是說腾它，2型文法是1型文法的特例。因此瞒滴，1型文法可識別的語言集合比2型文法可識別的語言集合更大，很明顯1型文法限制更加少了虏两，包括了2型文法

無約束文法（0型文法世剖，這個沒啥用，就是湊數(shù)的）

從0型文法到3型文法祖凫，對規(guī)則的約束越來越多惠况，每一個正則文法都是上下文無關(guān)文法宁仔，每一個上下無關(guān)文法都是上下文有關(guān)文法，而每一個上下文有關(guān)文法都可以認為是0型文法权埠。因此煎谍，從0型文法到3型文法所識別的語言集合越來越小

自動機

根據(jù)不同的構(gòu)成和功能，自動機分成以下4種類型：有限自動機（finite automata, FA）粱快、下推自動機（push-down automata, PDA）秩彤、線性界限自動機（linear-bounded automata）和圖靈機（Turing machine）

這個自動集合形式語言的四種文法有一一對應(yīng)的關(guān)系

0型文法對應(yīng)圖靈機

1型文法對應(yīng)線性有界自動機

2型文法對應(yīng)下推自動機

3型文法對應(yīng)正則文法

自動機也是研究自然語言處理的重要工具叔扼，不過今年大家用的比較多的是經(jīng)驗主義那一套，所以自動機相對來說用的比較少了漫雷，我們后面也用不到自動機這個工具瓜富，所以有興趣的同學(xué)可以找資料看看

END