樹狀自動機是一種類型的狀態機。樹狀自動機處理的是樹狀結構，而不是更傳統的狀態機的字符串。下面的文章涉及到分支樹自動機，它對應于樹的規則語言。與經典自動機一樣，有限樹自動機（FTA）可以是確定性自動機，也可以不是。根據自動機處理輸入樹的方式，有限樹自動機可以有兩種類型：（a）自下而上，（b）自上而下。這是一個重要的問題，因為盡管非確定性（ND）自上而下和ND自下而上的樹自動機在表達能力上是相等的，但是確定性自上而下的自動機嚴格來說比確定性自下而上的自動機要差，因為確定性自上而下的樹自動機所指定的樹屬性只能依賴于路徑屬性。(確定性的自下而上的樹自動機與ND樹自動機一樣強大）。

F上的自下而上有限樹自動機被定義為一個元組（Q,F,Qf,Δ），其中Q是一組狀態，F是一個有等級的字母表。

也就是說，Δ的成員是重寫規則，從節點的子根是狀態，到節點的根是狀態。因此，一個節點的狀態是由其子節點的狀態推導出來的。對于n=0，即對于常量符號f，上述過渡規則的定義為f()→q(f())；為了方便，通常省略空括號：f→q(f)。由于這些常量符號（葉子）的過渡規則不需要狀態，所以不需要明確定義初始狀態。一個自下而上的樹狀自動機在F上運行一個基礎項，同時從其所有葉子開始并向上移動，將Q的一個運行狀態與每個子項關聯。如果該項根與Qf的一個接受狀態關聯，則被接受。F上的自上而下的有限樹自動機被定義為一個元組（Q,F,Qi,Δ），與自下而上的樹自動機有兩個區別。

一個自上而下的自動機從根部的一些初始狀態開始，沿著樹的分支向下移動，沿著運行與每個子項歸納地關聯一個狀態。如果每個分支都能以這種方式通過，那么一棵樹就被接受。

如果沒有兩個來自Δ的規則具有相同的左手邊，則樹狀自動機被稱為確定性的。非確定性自上而下的樹狀自動機與非確定性自下而上的樹狀自動機具有相同的表達能力；過渡規則被簡單地顛倒，最終狀態成為初始狀態。相比之下，確定性的自上而下的樹形自動機比自下而上的自動機功能要小，因為在確定性的樹形自動機中，沒有兩個過渡規則的左手邊是相同的。對于樹狀自動機，過渡規則是重寫規則；而對于自上而下的自動機，左側將是父節點。因此，確定性的自上而下的樹型自動機只能測試在所有分支中都是真的樹型屬性，因為要寫入每個子分支的狀態的選擇是在父節點決定的，而不知道子分支的內容。

使用與上面相同的著色，這個例子顯示了樹形自動機是如何概括普通字符串自動機的。有限確定性字符串自動機接受所有表示3的倍數的二進制數字串。