學習書籍：統計自然語言處理（宗成慶）

理解筆記：

圖 樹 字符串

3.1 圖
3.1.1 無向圖
無向圖G可定義為一個二元組G=(N,E)，其中N為圖中頂點的集合，E為所有邊的集合，即兩個點之間的邊沒有方向。
3.1.2 有向圖
有向圖G可定義為一個二元組G=(N,E)，其中N為圖中頂點的集合，E為所有邊的集合，但（n_i,n_j）和（n_j,n_i）是兩條不同的邊。
3.1.3 連通圖
連通圖是一個有向圖或者無向圖，對于任意兩個頂點都能找到一個圖內的通路進行連接。（對于任意兩個點，有向圖需要找到兩個方向的通路，無向圖只需要一條通路）
3.3.4 回路
對于一個圖中，由n個頂點連成的通路，如果開始節點和結束節點是同一個節點，這條路徑稱為一個通路。

3.2 樹
森林：沒有回路的無向圖
樹：沒有回路的連通無向圖

3.3 字符串
字符串： 由字符集合中的字符連接組成的有限序列稱為字符集合上的字符串。
定義在字符串上的兩種運算：字符串連接和閉包運算。
字符串連接：x y是字符集上的字符串，把y接在x后面稱為x與y的連接，記作xy。
閉包運算：閉包有多種概念，其中包括集合的閉包，關系的閉包和編程中的閉包。參考閉包。字符串的閉包定義與上面也有所不同，具體參考書籍。（如果有理解錯誤，歡迎指出）

描述語言的三種方式

窮舉法，將語言中的所有句子都枚舉出來

文法描述（產生式系統）：描述語言及其結構，生成合法句子

自動機：對句子進行合法性檢驗，識別一個字符串是否屬于該語言

文法描述和自動機各有所長，自然語言處理中大多各取所長。

形式語言（文法描述）

由喬姆斯基的語法理論，文法被劃分為4種類型：3型文法（正則文法）、2型文法（上下文無關文法）、1型文法（上下文有關文法）、0型文法（無約束文法）。

1.正則文法

由定義可以看出，正則文法中所有的產生式的左式都是單個非終結符，右式是單個終結符或者（非終結符+終結符）。此種文法也被稱為左線性正則文法，若右式是單個終結符或者（終結符+非終結符），文法被稱為右線性正則文法。

2.上下文無關文法

由定義可以看出，上下文無關文法中所有的產生式都是單個非終結符，右式不做限制

3.上下文有關文法

由定義可以看出，產生式中需要上下文環境，當A左右的上下文環境都是空字符的時候，該上下文有關文法蛻變成無關文法，故上下文無關文法是上下文有關文法的一個特例。因此上下文有關文法比上下文無關文法識別的語言集合更大。

4.無約束文法

由定義可知，無約束文法對產生式沒有限制

自動機

自動機分為四種類型 有限自動機、下推自動機、線性界限自動機、圖靈機。

有限自動機

有限自動機可分為確定性有限自動機（DFA）和不確定性有限自動機（NFA）。

DFA和NFA的區別是，在DFA中，由一個輸入引起的狀態轉移是確定的，而在NFA中，由一個輸入引起的狀態轉移是一個狀態集合，即存在多種可能結果。

一個NFA總是可以找到一個等價的DFA。
正則文法和自動機：正則文法和自動機之間可以相互轉換。

**# 轉換方法，待學 **

下推自動機

下推自動機可以被形象的理解為，把有限狀態自動機擴展，附加了一個可以存取的棧。其中每一個下推自動機都接受一個形式語言。與有限自動機一樣，下推自動機存在確定和不確定兩種形式。（與有限自動機不一樣的是，DFA和NFA兩者是等價的，確定的下推自動機和不確定的下推自動機是不等價的）。其中，被不確定的下推自動機接受的語言是上下文無關語言。

由定義可知，下推自動機在有限自動機的基礎上增加了下推存儲器的符號集合和下推存儲器的初始狀態這兩個變量。當輸入一個字符時，不僅僅更新自動機的狀態，還更新下推存儲器的狀態。

判斷是否被下推自動機接受的標準有兩種。 （1）終止狀態接受標準 （2）空存儲器接受標準

總結

以上是生活随笔為你收集整理的NLP学习一 形式语言与自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。