Начало см. здесь.

Рассмотрим Дерево из предыдущего параграфа как размеченное упорядоченное дерево в смысле Ахо-Ульмана.

Тогда мы естественным образом сможем рассматривать его как диаграмму состояний некоторого автомата с конечной памятью. Множеством состояний этого автомата будут цепочки, которыми помечены вершины Дерева, а алфавит A будет состоять из двух символов V и H, которыми помечены дуги Дерева. Начальным состоянием автомата будет цепочка p, которой помечен корень, а множеством финальных состояний будут цепочки VVp, HVp, VHp, HHp, которыми помечены листья Дерева.