樹文法

具有一組生成規則（產生式）的樹語言(樹的集合)產生系統。樹文法是1969年W.S.布雷納德首先提出的。短語結構文法生成語言的特點是字元與字元間存在從左到右的一維連接關係（稱為鏈）。假使把一維的連接關係向多維推廣，就可能把鏈推廣為樹。圖中是樹的一例，其中標號為b的最上端節點是樹根，它有兩個標號分別為b和a的子節點。前者是樹葉，沒有子節點。後者是中間節點，有兩個標號為b的子節點，它們都是樹葉。一般情形下，一棵樹的樹根用α＝0表示，樹根的子節點依次用α＝1，2…表示，節點1的子節點依次用 α＝1·1，1·2，…表示，等等。由所有這些表示樹上的節點的α組成的集合，就是該樹的樹域。於是，以有限字母表∑的元素為標號的樹(簡稱∑上的樹)t,可以看成一個函數t: D-→∑,其中D是t的樹域；對於是樹t上的節點α 的標號；是t(α )的秩，即樹t上節點α 的子節點數。對於圖中的樹，,節點標號和對應的秩是：,

生成樹語言的一種常用文法是有秩字母表（∑,r）上的擴展樹文法$$,!!其中N是非終止符集;s∈N是起始符；P是產生式集。擴展樹文法的特點是P中的產生式具有形式：

這裡a屬於∑；屬於N；r(a)是a的秩。用T∑表示∑上全體樹的集合，由擴展樹文法Gt生成的樹語言是T∑的子集。由於樹中的符號具有多維連接關係，不少模式可以用樹來描述，從而得到一個樹文法。例如對於字元識別來說，若設a，b分別代表基元“-”和“│”,則英文字元H 對應有下列產生式的擴展樹文法Gt：

$$!!

一個可能的導出過程是：

$$!! 和它相應的圖形是：

上述Gt生成的樹語言可以描述各種尺寸的字元H 。不同的字元類對應不同的擴展樹文法，且可用樹自動機來進行識別。樹文法還可用於指紋圖像分析。

參考書目

K.S.Fu,Syntactic Pattern Recognition and Applications, Prentice-Hall，Englewood Cliffs, N.J.，1982.