嵌入下推自動機或 EPDA 是分析樹-鄰接文法(TAG)的計算模型。除了不再使用堆疊來存儲符號之外,它類似於分析上下文無關文法的下推自動機。它有存儲符號的重複堆疊組成的一個棧,這給予了 TAG 在上下文無關文法和上下文有關文法之間的複雜度,或者說是適度上下文有關文法的子集。
歷史和應用
EPDA 最初由 K. Vijay-Shanker 在他 1998 年的博士論文中描述[1]。它們已經被應用於更完整的描述適度上下文有關文法類,並向喬姆斯基層級擴展和精細了這個文法類。各種子文法,比如線性附標文法可以從而定義[2]。它們還在自然語言處理中扮演重要角色。
儘管自然語言有使用上下文無關文法來分析的傳統(參見轉換-生成語法和計算語言學),但這個模型不適合有交叉依賴的語言如荷蘭語,而 EPDA 就適合。詳細的語言分析可見於引文[3]。
理論
首先重申 EPDA 是有一組其自身可以通過「嵌入棧」來訪問的棧的有限狀態機,每個棧包含「棧字母表」
的元素,並且我們通過
定義一個棧的元素,這裏的星號是字母表的Kleene閉包。
每個棧都可以依據它的元素來定義,所以我們使用雙劍符號來指示在自動機中的第
個棧:
,這裏的
將是在棧中的下一個可訪問的符號。
個棧的「嵌入棧」因此可以指示為
。
我們定義 EPDA 為七元組
這裏的
是「狀態」的有限集合;
是「輸入字母表」的有限集合;
是「棧字母表」的有限集合;
是「開始狀態」;
只「最終狀態」的集合;
是「初始棧符號」
是「轉移函數」,這裏的
是
的有限子集。
所以轉移函數選取一個狀態,輸入字符串的下一個符號,和當前棧的頂符號;並生成下一個狀態,在「嵌入棧」上要壓入和彈出的那些棧,當前棧的壓入和彈出,和要在下一個轉移中被當作當前棧的棧。更加概念的說,「嵌入棧」是被壓入和彈出的,當前棧被隨意的壓回到「嵌入棧」,而你希望的任何其他棧將被壓入它的頂部,帶有最後的棧是在下一個重複中所讀取的。所以,這些棧被同時壓入當前棧的上面和下面。
一個給定的格局被定義為
![{\displaystyle \,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef2aaf931f7274f6f31a00daa1265e4ba6295771)
這裏的
是當前狀態,
是在「嵌入棧」中的棧,帶有
是當前棧,而對於輸入字符串
,
是已經被機器處理的那部分字符串,而
是要處理的那部分,帶有它的頭部是當前所讀的符號。注意空串
被隱含的定義為終止符號,如果機器處於最終狀態此時讀到空串,則整個輸入字符串被「接受」,如果不是則「拒絕」。這種「接受」了的字符串是如下語言的元素
![{\displaystyle \,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f87351d56443967b415308ee4f923de7bf984e9)
這裏的
而
定義轉移函數按需要而多次應用來分析這個字符串。
引用
|
---|
| | | 每個語言範疇都是其直接上面的範疇的真子集 每個語言範疇內的語言都可以用同一行的文法和自動機表示 |
|