文章目錄

• 1形式語言
• • 1.2形式語言
• 3推導
• • 3.1句型、句子、語言
  • 3.2文法
  • 3.3派生樹與二義性
• 4有限自動機和正則文法
• • 4.1確定的有限自動機DFA
  • 4.2不確定的有限自動機NFA
  • 4.3有限自動機<=>正則文法
• 5.下推自動機PDA和上下文無關文法CFG
• • 5.1PDA
  • • 5.1.1 PDA的例子.
  • 5.2 其他自動機
  • • 5.2.1 區別
• 6. 有限自動機在nlp中的應用
• • 6.1 英語單詞拼寫檢查
  • • 6.1.1 編輯距離
    • 6.1.2 有限狀態機
    • 6.1.3 深度優先搜索找路徑
  • 5.2 英語單詞形態分析
  • FA的變種
• 6.作業
• • 3.1
  • 3.2
  • 3.3
  • 3.4
  • 3.5
  • 3.6

1形式語言

• 語言：人類所特有的用來表達意思、交流思想的工具，是一種特殊的社會現象，由語音、詞匯和語法構成一定的系統。
• 語言描述的三種途徑
  • 窮舉法 — 只適合句子數目有限的語言。
  • 語法描述 — 生成語言中合格的句子。
  • 自動機 — 對輸入的句子進行檢驗，區別哪些是語言中的句子，哪些不是語言中的句子
• 形式語言：是用來精確地描述語言（包括人工語言和自然語言）及其結構的手段。形式語言學 也稱 代數語言學
  • 以重寫規則 $\alpha \to \beta$的形式表示，其中， $\alpha ,\beta$ 均為字符串。顧名思義：字符串 $\alpha$ 可以被改寫成 $\beta$ 。一個初步的字符串通過不斷地運用重寫規則，就可以得到另一個字符串。通過選擇不同的規則并以不同的順序來運用這些規則，就可以得到不同的新字符串。

1.2形式語言

• 形式語法：四元組$G=(N、\Sigma ,P,S)$
  • N：非終結符號（變量
  • $\Sigma ：$ 終結符號
  • $$\begin{gathered} N\cap \Sigma =?; \\ V=N\cup \Sigma :詞匯表 \end{gathered}$$
  • P：一組重寫規則的有限集合：$P=\{\alpha \to \beta \},其中\alpha ，\beta 是V中元素構成的串，但\alpha 至少有一個非終結符號：S\in N(初始符或句子符號）$
  • eg:
  • G=({ A,S},{0,1},P,S)
  • $$\begin{gathered} P:S\to 0A1, \\ 0A\to 00A1, \\ A\to 1 \end{gathered}$$

3推導

• 推導：

  • 設施一個文法，在$(N\cup \Sigma {)}^{?}$上定義關系$\stackrel{G}{=>}(直接派生或推導）：$
  • *推導：n>=1
  • +推導：n>=0
  • 推導：n=1
    
    

• 最左推導

• 最右推導（規范推導
  

3.1句型、句子、語言

• 句型與句子
  • 一些特殊類型的符號串$G=(N、\Sigma ,P,S)$的句子形式（句型）：
  • S是一個句子形式
  • 句型推出的也是一個句型
    • $$\begin{gathered} \alpha \beta \gamma 是一個句型， \\ 且有\beta \to \delta 是p的產生式， \\ 則\alpha \delta \gamma 也是一個句型 \end{gathered}$$
  • 句子：不含有非終結符的句型
  • 語言：L(G),G產生的所有句子

3.2文法

• 0型文法（無限制重寫系統，無約束文法）：$P:\alpha \to \beta ,字符串$（理論上的，無用處
• 1型文法（上下文有關文法CSG):$$\begin{gathered} P:\alpha A\beta \to \alpha \gamma \beta \\ A\in N,\alpha ,\gamma ,\beta \in (N\cup \Sigma {)}^{?},且\gamma 至少包含一個字符 \\ 另一種定義：ifx\to y,x\in (N\cup \Sigma {)}^{+},y\in (N\cup \Sigma {)}^{?},并且|y|\ge |x|(越推越長） \end{gathered}$$
• 2型文法（上下文無關文法CFG）：$P:A\to \alpha ,A\in N,\alpha \in (N\cup \Sigma {)}^{?}$
• 3型文法（正則文法）：$$\begin{gathered} P:A\to Bx|A\to x,A,B\in N，x\in \Sigma (左線性正則文法 \\ A\to xB(右線性正則文法） \end{gathered}$$
• 0-3,約束越來越大：$L(G3)?L(G2)?L(G1)?L(G0)$
  • 顯然，每一個正則文法都是上下文無關文法，每一個上下無關文法都是上下文有關文法，而每一個上下文有關文法都是0型文法
• 判別文法類別時，傾向于判別為約束最大的：
  • 如果一種語言能由幾種文法所產生，則把這種語言稱為在這幾種文法中受限制最多的那種文法所產生的語言。
    

3.3派生樹與二義性

• 2型文法（上下文無關）CFG 產生的語言句子的派生樹表示CFG產生一個句子的派生樹由如下
  步驟構成：
  • (1) 對于$x\in N\cup \Sigma$ 給一個標記作為節點, S 作為樹的根節點。
  • (2) 如果一個節點的標記為 A，并且它至少有一個除它自身
    以外的后裔，則$A\in N$。
  • (3) 如果一個節點的標記為 A，它的 k ( k > 0) 個直接后裔節 點按從左到右的次序依次標記為 A1, A2, …, Ak，則 A -> A1A2…Ak 一定是 P 中的一個產生式
• 上 下文無關文法的二義性
  • 一個文法 G，如果存在某個句子有不只一棵分析樹與之對應，那么稱這個文法是二義的
    
    

4有限自動機和正則文法

4.1確定的有限自動機DFA

• 確定的有限自動機M是一個五元組$$\begin{gathered} M=(\Sigma ,Q,\delta ,q_0,F) \\ \Sigma :輸入符號的有窮集合 \\ Q：狀態的有限集合 \\ {q}_0\in Q:初始狀態 \\ F：終止狀態集合，F?Q \\ \delta :是Q\times \Sigma 到Q的映射，它支配著有限狀態控制的行為，狀態轉移函數 \end{gathered}$$
• $從q_0開始（輸入頭開始在最左邊），輸入a，q^{\prime }=\delta (q,a)，從q轉移到狀態q^{\prime }，并將輸入頭向右移動一個字符$
• 狀態變換圖如下：

• DFA所定義的語言
  • 可接受：$如果有一個句子x，使得\delta (q_0,x)=p,p\in F,則x可被M接受$
  • KaTeX parse error: Undefined control sequence: \inF at position 23: …x|\delta(q_0,x)\?i?n?F?\}
• 確定的：接受一個輸入，只會從一個狀態轉換到另一個狀態，不會有其他可能
  

4.2不確定的有限自動機NFA

• 不確定的有限自動機M是一個五元組$$\begin{gathered} M=(\Sigma ,Q,\delta ,q_0,F) \\ \Sigma :輸入符號的有窮集合 \\ Q：狀態的有限集合 \\ {q}_0\in Q:初始狀態 \\ F：終止狀態集合，F?Q \\ \delta :是Q\times \Sigma 到Q的冪集2^Q的映射，狀態轉移函數 \end{gathered}$$–區別在這里
• 區別：
  • $\delta (q,a)$
    • 在DFA中是一個狀態
    • 在NFA中是一個狀態集合
      
• 不確定性：$\delta (q_0,0)=q_3，q_0$
• 關系：設 L 是一個被 NFA 所接受的句子的集合，則存在一個 DFA，它能夠接受 L。
  • 由于 DFA 與 NFA 所接受的是同樣的鏈集，所以一般情況下無需區分它們，二者統稱為有限自動機 (finite automata, FA)。
  • 可以轉化

4.3有限自動機<=>正則文法

• 正則文法和FA等價
  • 若$G=(V_N,V_T,P,S)$是一個正則文法，則必然存在一個有限自動機$M=(\Sigma ,Q,\delta ,q_0,F)$,使得T(M)=L(G)
  • 若Ms是一個有限自動機，則必然存在正則文法G,L(G)=T(M)
• 由正則文法構造有限自動機M：
• 令$\Sigma =V_T,Q=V_N\cup T,q_0=S,其中，T是一個新增加的非終結符號$
• 如果P中有：$S\to ?,則，F=\{S,T\}，否則，F=\{T\}$
• 如果P中有：$B\to a,B\in V_N,a\in V_T,則T\in \delta (B,a)$
• 如果P有$B\to aC,B、C\in V_N,a\in V_T,則C\in \delta (B,a)$
• 對于每一個$a\in V_T,有\delta (T,a)=?$
  
• 由有限自動機M構造正則文法G：
• 令$V_N=Q,V_T=\Sigma ,S=q_0$
• $如果C\in \delta (B,a),B,C\in Q,a\in \Sigma ，則P:B\to aC$
• $如果C\in \delta (B,a),B,C\in F,a\in \Sigma ，則P:B\to a$

5.下推自動機PDA和上下文無關文法CFG

5.1PDA

• 下推自動機PDA：PDA 可以看成是一個帶有附加的下推存儲器的有限自動機，下推存儲器是一個棧
  • 一個不確定的PDA可以表達成一個7元組$$\begin{gathered} M=(\Sigma ,Q,\Gamma ,\delta ,q_0,Z_0,F) \\ \Sigma :輸入符號 \\ Q:狀態的有限集合 \\ {q}_0\in Q：初始狀態 \\ \Gamma :下推存儲器符號的有窮集合 \\ {Z}_0\in \Gamma :為最初出現在下推存儲器頂端的符號 \\ F:終止狀態集合，F?Q \\ \delta 是從Q\times (\Sigma \cup \{?\})\times \Gamma 到Q\times {\Gamma }^{?}子集的映射 \end{gathered}$$
    
• 映射關系\delta的解釋
  • $\delta (q,a,Z)=\{(q_1,{\gamma }_1).(q_2,{\gamma }_2),...(q_m,{\gamma }_m)\},q\in Q,a\in \Sigma ,\gamma \in {\Gamma }^{?}$
  • 當PDA處于狀態 q，面臨輸入符號a 時，自動機將進入 qi , i = 1, 2, …, m 狀態，并以${\gamma }_i$ 來代替下推存儲器(棧)頂端符號Z，同時將輸入頭指向下一個字符 。當 Z 被${\gamma }_i$取代時，${\gamma }_i$ 的符號按照從左到右的順序依次從下向上推入到存儲器。
  • 特殊情況$?移動：a=?$,輸入頭位置不移動，只用于處理下推存儲器內部的操作
• 符號約定
  • 合法轉移：設有序對$(q,\gamma ),q\in Q,\gamma \in {\Gamma }^{?},對于a\in (\Sigma \cup \{?\})是輸入字符,\beta \in {\Gamma }^{?},Z\in F,如果(q^{\prime },\beta )\in \delta (q,a,Z),q^{\prime },q\in Q$
    
  • 0次或多次合法轉移：*推
• PDA M可以接受的語言為：
  • 接受收入并可到達一個可接受狀態
    

5.1.1 PDA的例子.

輸入串是從左到右依次輸入的
入棧出棧都走左邊進出

5.2 其他自動機

• 圖靈機
  • 圖靈機與0型文法等價；
  • 圖靈機與有限自動機(FA)的區別：圖靈機可以通過其讀/寫頭改變輸入帶的字符。
  • 僅存在概念，太靈活了
• 線性帶限自動機
  • 線性帶限自動機與1型文法等價；
  • 線性帶限自動機是一個確定的單帶圖靈機，其讀 寫頭不能超越原輸入帶上字符串的初始和終止位置，即線性帶限自動機的存儲空間被輸入符號串的長度所限制。

5.2.1 區別

• 各類自動機的主要區別是它們能夠使用的信息存儲空間的差異：
  • 有限狀態自動機只能用狀態來存儲信息；
  • 下推自動機除了可以用狀態以外，還可以用下推存儲器(棧)；
  • 線性帶限自動機可以利用狀態和輸入/輸出帶本身。因為輸入/輸出帶沒有**“先進后出”**的限制，因此，其功能大于棧；
  • 而圖靈機的存儲空間沒有任何限制。
    

6. 有限自動機在nlp中的應用

6.1 英語單詞拼寫檢查

6.1.1 編輯距離

• 編輯距離
  • 設 X 為拼寫錯誤的字符串，其長度為m, Y 為 X 對應的正確的單詞(答案)，其長度為 n。則 X 和 Y 的編輯距離ed(X[m], Y[n]) 定義為：從字符串 X轉換到 Y 需要的插入、刪除、替換和交換兩個相鄰的基本單位(字符)的最小個數。如：
    • ed (recoginze, recognize) = 1
    • ed (sailn, failing) = 3
• 假設 Z = z1 z2 … zp 為字母表 A上的p 個字母構成
  的字符串，Z[j] 表示含有j (j >= 1) 個字符的子串。X[m] 為拼寫錯誤的字符串，其長度為m，Y[n] 為與X串接近的字符串(一個候選)，其長度為n。則給定兩個串X 和Y的編輯距離ed(X[m], Y[n]) 可以通過循環計算出從字符串X 轉換到Y 需要進行插入、刪除、替換和交換兩個相鄰的字符操作的最少次數
  • (1) 如果 $x_{i+1}=y_{j+1}$（兩個串的最后一個字母相同），
    • 則 ed(X[i+1], Y[j+1]) = ed(X[i], Y[j]);
  • (2) 如果 $x_i=y_{j+1}$，并且 $x_{i+1}=y_j$（最后兩個字符需要
    交換位置），
    • 則ed(X[i+1], Y[j+1]) = 1+min{ed(X[i-1], Y[j-1]),ed(X[i], Y[j+1]),ed(X[i+1], Y[j])}
      

*（3）其他情況($x_{i+1}=y_{j+1}并且(x_i=y_{j+1}或x_{i+1}=y_j）$

• ed(X[i+1], Y[j+1]) = 1+min{ed(X[i], Y[j]),ed(X[i], Y[j+1]),ed(X[i+1], Y[j])}
• 其中：
  • ed(X[0],Y[j])=j (0<=j<=n)X長度為0
  • ed(X[i],Y[0])=i,(0<=i<=m
  • 邊界約定：ed(X[-1],Y[j])=ed(X[i],Y[-1])=max{m,n}
    

6.1.2 有限狀態機

• 有時候要在自動機上做改變
  • $$\begin{gathered} R=(Q,A,\delta ,q_0,F) \\ Q:狀態集 \\ A：輸入集 \\ \delta :Q\times A\to Q \\ {q}_0\in Q：起始狀態 \\ F?Q：終止狀態集 \end{gathered}$$
• $L?A^{?}$是R接受的語言，字母構成的所有合法單詞都是有限狀態機中的一條路徑。給定一個輸入串，對其進行檢查的過程就是在給定閾值 t (t > 0) 的情況下，尋找那些與輸入串的編輯距離小于 t 的路徑。那么，一個字符串$X[m]\in /L$ 能夠被 R識別的條件是存在非空集合
  $$C=\{Y[n]|Y[n]\in L\&ed(X[m],Y[n])\le t\}$$

中間有共用的單詞

• 定義：$$\begin{gathered} cuted(X[m],Y[n])=mi{n}_{l\le i\le u}\{ed(X[i],Y[n])\} \\ l=max(1,n?t),u=min(m,n+t) \end{gathered}$$
  • t的用途：
    • 確定截取X的范圍
    • 限定編輯距離

6.1.3 深度優先搜索找路徑

• Y是合法的單詞，X是輸入的單詞(可能是錯的詞），找與X最接近的合法詞匯
• 采用深度優先搜索算法從自動機中選擇路徑。假設X=bax, t=2。那么，Y=a/b/c/…/z，l=max{1, 1-2}=1， u=min{3, 1+2}=3。即從 X 中取長度在1～3個字符范圍內的子串X’＝{b, ba, bax}，分別計算與 Y 之間的編輯距離，保留那些 ed(X’, Y)≤ t 的路徑，選擇 ed 最小的路徑繼續擴展。
• X=bax, t=2。 Y={ba, bi, bo, … …}。
  • 截取 X: l=max{1, 2-2}=1, u=min{3, 2+2}=3。 X’={b, ba, bax}
  • 保留那些 ed(X’, Y)≤ t 的路徑，選擇 ed 最小的路徑繼續擴展。
• X=bax, t=2。Y={baa, bad, bag, bat, bay}。
  • 截取 X: l=max{1, 3-2}=1, u=min{3, 3+2}=3。 X’={b, ba, bax}
  • 保留那些 ed(X’, Y)≤ t 的路徑，選擇 ed 最小的路徑，繼續擴展Y。
• X=bax, t=2。Y={bade}。
  • 截取 X: l=max{1, 4-2}=2, u=min{3, 4+2}=3。 X’={ba, bax}
  • 保留那些 ed(X’, Y)≤ t 的路徑，選擇 ed 最小的路徑

• 深度優先可能有只能得到一個解，不一定最優，但肯定
• 寬度優先：可以得到最短的解
• 算法
  

5.2 英語單詞形態分析

• 單復數
• 時態
• 比較
  
• 一般地，具有相同的前綴或詞根，詞綴不同的單詞可以共用一個有限狀態轉移機，共享其中的某些狀態節點。如：tie, ties, trap, traps, try, tries, to, torch, torches, toss, tosses 等。
• 除了單詞拼寫檢查、形態分析以外，有限狀態自動機還廣泛應用于詞性標注、句法分析、短語識別、機器翻譯和語音識別等很多方面。

FA的變種

• 有限自動機FA：只實現狀態轉移，不產生任何輸出
• 有限狀態機FSM：只實現狀態轉移，不產生任何輸出
• 有限狀態轉換機FST：完成狀態轉移的同時產生一個輸出

6.作業

3.1

3.2

$a^n{b}^n{c}^n,n\ge 1$

3.3

3.4

3.5

3.6

總結

以上是生活随笔為你收集整理的nlp3-有限自动机FLandFA的全部內容，希望文章能夠幫你解決所遇到的問題。

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