树（自动机理论）

在自动机理论中，树是以自然数的序列来表示树结构的一种特殊方式。这有助于这个定义在自动机理论中的应用。{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形成一个（完全）无限二叉树。