嵌入下推自動機

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

基本介紹

• 中文名：嵌入下推自動機
• 縮寫：EPDA
• 性質：計算模型
• 領域：計算機

歷史和套用

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

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

理論

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

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

我們定義 EPDA 為七元組：

這裡的

是“狀態”的有限集合；

是“輸入字母表”的有限集合；

是“棧字母表”的有限集合；

是“開始狀態”；

只“最終狀態”的集合；

是“初始棧符號”

是“轉移函式”，這裡的 是 的有限子集。

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

一個給定的格局被定義為

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

計算模型

計算模型（computational model）是計算科學中的一個數學模型，它使用大量的計算資源來用計算機模擬研究一個複雜系統的行為。被研究的系統通常是一個複雜的非線性系統，這種系統不易取得簡單、直觀的解析解。相比於推導數學分析來解決問題，它是通過在計算機中調整系統參數並研究實驗結果的差異來完成模型。模型的操作理論可以從這些實驗來推斷/推導。

常見的計算模型有天氣預報模型、地球模擬器模型、飛行模擬器模型、分子蛋白質摺疊模型和神經網路模型。

上下文有關文法

上下文有關文法(CSG，英語：context-sensitive grammar)是一種形式文法，其中任何產生式規則的左手端和右手端都可以被終結符和非終結符構成的上下文所圍繞。上下文有關文法比上下文無關文法更一般性，但仍足夠有秩序得可以被線性有界自動機所解析。

上下文有關文法的概念是諾姆·喬姆斯基在1950年代介入的，被作為描述自然語言的語法的一種方式，在自然語言中一個單詞是否可以出現在特定位置上，要依賴於上下文。可以被上下文有關文法描述的形式語言叫做上下文有關語言。