Una macchina a stati finiti deterministico che accetta alberi infiniti, piuttosto che 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. Potenza l'espressivo di tali automi varia a seconda delle condizioni di accettazione degli alberi.