Tree (automata theory)

For example, each node of the tree is a word over set of natural numbers (

, then t ∈ T and t.c1 ∈ T for all 0 ≤ c1 < c. The elements of T are known as nodes, and the empty word ε is the (single) root of T. For every t ∈ T, the element t.c ∈ T is a successor of t in direction c. The number of successors of t is called its degree or arity, and represented as d(t).

A path may be a finite or infinite set.

In the case of ranked alphabets, an extra function Ar: Σ →

This function associates a fixed arity to each symbol of the alphabet.

The trees that do not (necessarily) satisfy that property are called unranked.

It is clear from the picture that T forms a (fully) infinite binary tree.