嵌入下推自動機

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

歷史和應用

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

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

理論

首先重申 EPDA 是有一組其自身可以通過「嵌入棧」來訪問的棧的有限狀態機，每個棧包含「棧字母表」 $\Gamma \,$ 的元素，並且我們通過 $\,\sigma _{i}\in \Gamma ^{*}$ 定義一個棧的元素，這裏的星號是字母表的Kleene閉包。

每個棧都可以依據它的元素來定義，所以我們使用雙劍符號來指示在自動機中的第 $\,j$ 個棧: $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$，這裏的 $\,\sigma _{k}$ 將是在棧中的下一個可訪問的符號。$\,m$ 個棧的「嵌入棧」因此可以指示為 $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$。

我們定義 EPDA 為七元組

$\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})$ 這裏的

• $\,Q$ 是「狀態」的有限集合；
• $\,\Sigma$ 是「輸入字母表」的有限集合；
• $\,\Gamma$ 是「棧字母表」的有限集合；
• $\,q_{0}\in Q$ 是「開始狀態」；
• $\,Q_{\textrm {F}}\subseteq Q$ 只「最終狀態」的集合；
• $\,\sigma _{0}\in \Gamma$ 是「初始棧符號」
• $\,\delta :Q\times \Sigma \times \Gamma \rightarrow S$ 是「轉移函數」，這裏的 $\,S$ 是 $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ 的有限子集。

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

一個給定的格局被定義為

$\,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}$

這裏的 $\,q$ 是當前狀態，$\,\Upsilon$ 是在「嵌入棧」中的棧，帶有 $\,\Upsilon _{m}$ 是當前棧，而對於輸入字符串 $\,x=x_{1}x_{2}\in \Sigma ^{*}$, $\,x_{1}$ 是已經被機器處理的那部分字符串，而 $\,x_{2}$ 是要處理的那部分，帶有它的頭部是當前所讀的符號。注意空串 $\,\epsilon \in \Sigma$ 被隱含的定義為終止符號，如果機器處於最終狀態此時讀到空串，則整個輸入字符串被「接受」，如果不是則「拒絕」。這種「接受」了的字符串是如下語言的元素

$\,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}$

這裏的 $\,q_{\textrm {F}}\in Q_{\textrm {F}}$ 而 $\,\rightarrow _{M}^{*}$ 定義轉移函數按需要而多次應用來分析這個字符串。