Una extensión de una máquina de Estados finitos que opera en n-arios constructores. Donde un autómata de Estados finitos alcanza un nuevo estado con un solo Estado y carácter, un autómata de árbol toma n Estados y constructores. Autómatas árbol pueden ser top-down (a partir de la raíz) o bottom-up (a partir de las hojas) y determinista o no determinista.