Une machine à états finis déterministes qui accepte les arbres finitiste plutôt que seulement les chaînes. L'arborescence de nœuds sont marqués par les lettres de l'alphabet de l'automate, et la fonction de transition encode les États suivants pour chaque branche de l'arbre. Condition de l'acceptation est modifiée en conséquence.