樹-鄰接文法

樹-鄰接文法(TAG)是 Aravind Joshi 定義的文法形式化。樹-鄰接（adjoining）文法在某種意義上類似於上下文無關文法，但是基本的重寫單位是樹而不是符號。上下文無關文法有把符號重寫為其他符號的規則，而樹-毗連文法有把樹的節點重寫為其他樹的規則。

文法規則

TAG 中的規則是帶有叫做「足節點」的特殊葉子的樹，它們錨接（anchor）到一個字。在 TAG 中有兩個種類的基本樹：「初始」樹（經常被表示為 '${\displaystyle \alpha }$'）和「輔助」樹（'${\displaystyle \beta }$'）。初始樹表示基本的價（valency）關係，而輔助樹允許遞歸。^[1] 輔助樹有標記（label）上同樣符號的根（頂）節點和足節點。推導開始於初始樹，通過要麼「代換」要麼「附加」來結合。代換把末梢節點替換為其頂節點有同樣符號的另一個樹。附加把一個輔助樹插入到另一個樹的中心。^[2] 輔助樹的根／足標記必須匹配它所鄰接的節點的標記。其他 TAG 的變體允許多種成分的樹，帶有多個足節點的樹，和其他擴展。

樹-鄰接文法經常被描述為「適度上下文有關的」，這意味著它們有（在弱生成能力方面上）特定性質使其有比上下文無關文法更強力，但有比附標文法或上下文有關文法更弱的能力。適度上下文有關文法被推測為足夠強力可以建模自然語言，而仍保持在一般情況下有效解析。^[3] 由於它們的形式特性，TAG 經常被用於計算語言學和自然語言處理。

文法緣起

TAG 起源於 Joshi 和他的學生對附加文法（AG）家族和 Zellig Harris 的「字符串文法」的研究 ^[4] 。AG 以自然和高效的方式處理語言的向心（英語：Endocentric and exocentric）性質，但是沒有對離心構造的好特徵描述；重寫文法或短語-結構文法（PSG）正好反過來。在 1969 年，Joshi 通過混合兩種類型的規則介入了開拓出這種補足的文法家族。一些非常簡單的重寫規則足夠生成附加規則的字符串的詞彙表。這個家族不同於喬姆斯基層級，但是有所交疊。^[5]

TAG 可以描述有平方的語言（在其中某個任意字符串被重複），和語言 ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$，有立方的語言（就是三倍的字符串）或有相等長度的多於四個不同字符的字符串的語言不可以被樹-鄰接文法所生成。為此，樹-毗連文法生成的語言被稱為「適度上下文有關語言」。