Una macchina a stati finiti deterministico che accetta finitaria alberi anziché soli stringhe. Nodi dell'albero sono contrassegnati con le lettere dell'alfabeto dell'automa, e la funzione di transizione codifica degli stati successivi per ogni ramo dell'albero. L'accettazione condizione verrà modificato di conseguenza.