樹（自動機理論）

在自動機理論中，樹是以自然數的序列來表示樹結構的一種特殊方式。這有助于這個定義在自動機理論中的應用。{displaystyle{mathbb{N}}和c∈N}T的元素被稱為節點，空詞ε是T的（單一）根。對于每個t∈T，元素t.c∈T是t在c方向上的繼承者。如果一個節點沒有繼承者，它就是一個葉子。如果一棵樹的每個節點都有有限的繼任者，那么它就被稱為有限分支樹，否則就是無限分支樹。路徑π是T的一個子集，使得ε∈π，對于每一個t∈T，要么t是葉子，要么存在一個xxx的c∈T一個路徑可以是一個有限或無限的集合。如果一棵樹的所有路徑都是有限的，那么這棵樹就叫做有限的，否則就是無限的。如果一棵樹的所有路徑都是無限的，則稱為完全無限的。給定一個字母表Σ，一個Σ標記的樹是一對(T,V)，其中T是一棵樹，V:T→Σ將T的每個節點映射到Σ中的一個符號。

標簽樹正式定義了一個常用的術語樹結構。一組標記的樹被稱為樹語言。如果一個樹的每個節點的后繼者之間有一個順序，那么這個樹被稱為有序的。上述樹的定義自然地暗示了繼承者之間的順序，這可以用來使樹有一個排名。在排序字母表的情況下，一個額外的函數Ar:Σ→被定義了。這個函數為字母表的每個符號關聯了一個固定的節數。在這種情況下，每個t∈T必須滿足Ar(V(t))=d(t)。滿足這一屬性的樹被稱為有等級的樹。不（一定）滿足該屬性的樹被稱為無等級的。例如，上述定義被用于無限樹自動機的定義中。

讓T={0,1}*，Σ={a,b}。我們定義一個標簽函數V如下：根節點的標簽是V(ε)=a，對于每一個其他節點t∈{0,1}*，其后續節點的標簽是V(t.0)=a和V(t.1)=b.從圖中可以看出，T形成一個（完全）無限二叉樹。