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

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

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

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

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

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

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

形式語法的定義

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

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

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

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

上下文無關文法（對的，還有上下文有關文法）

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

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

上下文有關文法（1型文法）

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

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

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

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

自動機

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

這個自動集合形式語言的四種文法有一一對應的關系

0型文法對應圖靈機

1型文法對應線性有界自動機

2型文法對應下推自動機

3型文法對應正則文法

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

END