嵌入下推自動機

嵌入下推自動機EPDA 是分析樹-鄰接文法(TAG)的計算模型。除了不再使用堆棧來存儲符號之外,它類似於分析上下文無關文法下推自動機。它有存儲符號的重複堆棧組成的一個棧,這給予了 TAG 在上下文無關文法和上下文有關文法之間的複雜度,或者說是適度上下文有關文法的子集。

歷史和應用

編輯

EPDA 最初由 K. Vijay-Shanker 在他 1998 年的博士論文中描述[1]。它們已經被應用於更完整的描述適度上下文有關文法類,並向喬姆斯基層級擴展和精細了這個文法類。各種子文法,比如線性附標文法可以從而定義[2]。它們還在自然語言處理中扮演重要角色。

儘管自然語言有使用上下文無關文法來分析的傳統(參見轉換-生成語法計算語言學),但這個模型不適合有交叉依賴的語言如荷蘭語,而 EPDA 就適合。詳細的語言分析可見於引文[3]

理論

編輯

首先重申 EPDA 是有一組其自身可以通過「嵌入棧」來訪問的棧的有限狀態機,每個棧包含「棧字母表」   的元素,並且我們通過   定義一個棧的元素,這裡的星號是字母表的Kleene閉包

每個棧都可以依據它的元素來定義,所以我們使用雙劍符號來指示在自動機中的第   個棧:  ,這裡的   將是在棧中的下一個可訪問的符號。  個棧的「嵌入棧」因此可以指示為  

我們定義 EPDA 為七元組

  這裡的
  •   是「狀態」的有限集合;
  •   是「輸入字母表」的有限集合;
  •   是「棧字母表」的有限集合;
  •   是「開始狀態」;
  •   只「最終狀態」的集合;
  •   是「初始棧符號」
  •   是「轉移函數」,這裡的    的有限子集。

所以轉移函數選取一個狀態,輸入字符串的下一個符號,和當前棧的頂符號;並生成下一個狀態,在「嵌入棧」上要壓入和彈出的那些棧,當前棧的壓入和彈出,和要在下一個轉移中被當作當前棧的棧。更加概念的說,「嵌入棧」是被壓入和彈出的,當前棧被隨意的壓回到「嵌入棧」,而你希望的任何其他棧將被壓入它的頂部,帶有最後的棧是在下一個重複中所讀取的。所以,這些棧被同時壓入當前棧的上面和下面。

一個給定的格局被定義為

 

這裡的   是當前狀態,  是在「嵌入棧」中的棧,帶有   是當前棧,而對於輸入字符串  ,   是已經被機器處理的那部分字符串,而   是要處理的那部分,帶有它的頭部是當前所讀的符號。注意空串   被隱含的定義為終止符號,如果機器處於最終狀態此時讀到空串,則整個輸入字符串被「接受」,如果不是則「拒絕」。這種「接受」了的字符串是如下語言的元素

 

這裡的    定義轉移函數按需要而多次應用來分析這個字符串。

引用

編輯
  1. ^ Vijay-Shanker, K. A Study of Tree-Adjoining Grammars. Ph.D. Thesis (University of Pennsylvania). January 1988. 
  2. ^ Weir, David J. Linear Iterated Pushdowns. Computational Intelligence. 1994, 10: 431––439 [2007-11-21]. (原始內容存檔於2007-02-16). 
  3. ^ Joshi, Aravind K.; Yves Schabes. Tree-Adjoining Grammars (PDF). Handbook of Formal Languages (Springer). 1997, 3: 69––124 [2007-11-21]. (原始內容 (PDF)存檔於2007-02-05).