ออโตมาตาแบบต้นไม้เป็นประเภทหนึ่งของเครื่องจักรสถานะออโตมาตาแบบต้นไม้ทำงานกับโครงสร้างแบบต้นไม้ แทนที่จะเป็น สตริงเหมือนเครื่องจักรสถานะทั่วไป

บทความต่อไปนี้กล่าวถึงออโตมาตาแบบแตกแขนงของต้นไม้ ซึ่งสอดคล้องกับภาษาปกติของต้นไม้

เช่นเดียวกับออโตมาตาแบบคลาสสิก ออโตมาตาต้นไม้จำกัด (FTA) สามารถเป็นออโตมาตาแบบกำหนดได้หรือไม่ก็ได้ ขึ้นอยู่กับวิธีที่ออโตมาตาประมวลผลต้นไม้ที่ป้อนเข้ามา ออโตมาตาต้นไม้จำกัดสามารถแบ่งออกได้เป็นสองประเภท: (ก) จากล่างขึ้นบน (ข) จากบนลงล่าง นี่เป็นประเด็นสำคัญ เพราะถึงแม้ว่าออโตมาตาต้นไม้แบบจากบนลงล่างและแบบจากล่างขึ้นบนที่ไม่กำหนด (ND) จะมีพลังในการแสดงออกที่เทียบเท่ากัน แต่ออโตมาตาแบบจากบนลงล่างที่กำหนดได้นั้นมีพลังน้อยกว่าออโตมาตาแบบจากล่างขึ้นบนที่กำหนดได้อย่างเคร่งครัด เนื่องจากคุณสมบัติของต้นไม้ที่ระบุโดยออโตมาตาต้นไม้แบบจากบนลงล่างที่กำหนดได้นั้นขึ้นอยู่กับคุณสมบัติของเส้นทางเท่านั้น (ออโตมาตาต้นไม้แบบจากล่างขึ้นบนที่กำหนดได้นั้นมีพลังเท่ากับออโตมาตาต้นไม้แบบไม่กำหนด)

ออโตมาตาต้นไม้จำกัดแบบล่างขึ้นบนบนFถูกกำหนดให้เป็นทูเปิล ( Q , F , Q _f , Δ) โดยที่Qคือเซตของสถานะ, Fคือตัวอักษรที่มีลำดับ (กล่าวคือ ตัวอักษรที่มีสัญลักษณ์ที่มีจำนวนสมาชิก ที่เกี่ยวข้อง ), Q _f ⊆ Qคือเซตของสถานะสุดท้าย และ Δ คือเซตของกฎการเปลี่ยนสถานะในรูปแบบf ( q ₁ ( x ₁ ),..., q _n ( x _n )) → q ( f ( x ₁ ,..., x _n )) สำหรับf ∈ F ที่มีสมาชิก nตัว, q , q _i ∈ Qและx _iเป็นตัวแปรที่แสดงถึงต้นไม้ย่อย กล่าวคือ สมาชิกของ Δ คือกฎการเขียนใหม่จากโหนดที่มีรากของโหนดลูกเป็นสถานะ ไปยังโหนดที่มีรากเป็นสถานะ ดังนั้น สถานะของโหนดจึงถูกอนุมานจากสถานะของโหนดลูก

สำหรับn = 0 นั่นคือสำหรับสัญลักษณ์คงที่fคำจำกัดความของกฎการเปลี่ยนผ่านข้างต้นอ่านว่าf () → q ( f ()); บ่อยครั้งที่วงเล็บว่างจะถูกละเว้นเพื่อความสะดวก: f → q ( f ) เนื่องจากกฎการเปลี่ยนผ่านเหล่านี้สำหรับสัญลักษณ์คงที่ (ใบ) ไม่ต้องการสถานะ จึงไม่จำเป็นต้องมีสถานะเริ่มต้นที่กำหนดไว้อย่างชัดเจน ออโตมาตาต้นไม้แบบล่างขึ้นบนจะทำงานบนเทอมพื้นฐานเหนือFโดยเริ่มจากใบทั้งหมดพร้อมกันและเคลื่อนที่ขึ้นไป โดยเชื่อมโยงสถานะการทำงานจากQกับเทอมย่อยแต่ละเทอม เทอมจะได้รับการยอมรับหากรากของมันเชื่อมโยงกับสถานะที่ยอมรับจากQ _f ^{[ 1 ]}

ออโตมาตาต้นไม้จำกัดแบบบนลงล่างบนFถูกนิยามเป็นทูเปิล ( Q , F , Qi _, Δ) โดยมีความแตกต่างสองประการกับออโตมาตาต้นไม้แบบล่างขึ้นบน ประการแรกQi _⊆ Qซึ่งเป็นเซตของสถานะเริ่มต้น จะแทนที่_Qf ประการ _{ที่สอง กฎ}การเปลี่ยนสถานะของมันมีทิศทางตรงกันข้าม: q ( f ( x1 ,..., xn _{) )} → f ( q1 ( x1 ),..., qn ( xn _{) )}สำหรับf ∈ F _{ที่ มี}nตัวแปร, q , Qi ∈ _QและXi ที่แสดงถึงต้นไม้ย่อย กล่าวคือ _{สมาชิก ของ Δ ในที่นี้คือกฎการเขียนใหม่จากโหนดที่มีรากเป็นสถานะไป} ยังโหนดที่มีรากของลูกเป็นสถานะ ออโตมาตาแบบบนลงล่างเริ่มต้นในสถานะเริ่มต้นบางส่วนที่รากและเคลื่อนที่ลงไปตามกิ่งก้านของต้นไม้ โดยเชื่อมโยงสถานะกับแต่ละเทอมย่อยแบบอุปนัยตลอดการเคลื่อนที่ ต้นไม้จะได้รับการยอมรับก็ต่อเมื่อทุกกิ่งก้านสามารถผ่านไปได้ด้วยวิธีนี้^{[ 2 ]}

ออโตมาตาต้นไม้เรียกว่าแบบกำหนด (ย่อว่าDFTA ) หากไม่มีกฎสองข้อใดจาก Δ ที่มีด้านซ้ายเหมือนกัน มิฉะนั้นจะเรียกว่าแบบไม่กำหนด ( NFTA ) ^{[ 3 ]}ออโตมาตาต้นไม้แบบบนลงล่างที่ไม่กำหนดมีพลังการแสดงออกเช่นเดียวกับแบบล่างขึ้นบนที่ไม่กำหนด^{[ 4 ]}กฎการเปลี่ยนสถานะจะถูกกลับกัน และสถานะสุดท้ายจะกลายเป็นสถานะเริ่มต้น

ในทางตรงกันข้ามออโตมาตาต้นไม้แบบบนลงล่างเชิงกำหนด^{[ 5 ]}มีประสิทธิภาพน้อยกว่าออโตมาตาต้นไม้แบบล่างขึ้นบน เนื่องจากในออโตมาตาต้นไม้เชิงกำหนด กฎการเปลี่ยนสถานะสองข้อจะไม่เหมือนกันทางด้านซ้าย สำหรับออโตมาตาต้นไม้ กฎการเปลี่ยนสถานะคือกฎการเขียนใหม่ และสำหรับแบบบนลงล่าง ด้านซ้ายจะเป็นโหนดแม่ ดังนั้น ออโตมาตาต้นไม้แบบบนลงล่างเชิงกำหนดจะสามารถทดสอบคุณสมบัติของต้นไม้ที่เป็นจริงในทุกสาขาเท่านั้น เพราะการเลือกสถานะที่จะเขียนลงในแต่ละสาขาย่อยจะถูกกำหนดที่โหนดแม่ โดยไม่ทราบเนื้อหาของสาขาย่อย ตัวอย่างเช่น ถ้าFประกอบด้วยf , gและaซึ่งเป็น 2ary, 1ary และ 0ary ตามลำดับ เซตของเทอมทั้งหมดที่มีอินสแตนซ์พื้นฐานของf ( a , g ( x )) เป็นเทอมย่อย สามารถรับรู้ได้โดย DFTA แบบล่างขึ้นบน แต่ไม่ใช่โดย DFTA แบบบนลงล่าง^{[ a ] ​​[ 6 ]}

ออโตมาตาต้นไม้อนันต์ขยายออโตมาตาแบบบนลงล่างไปยังต้นไม้อนันต์ และสามารถใช้เพื่อพิสูจน์ความสามารถในการตัดสินใจของS2Sซึ่ง เป็นทฤษฎี ลำดับที่สองแบบเอกภาคที่มีผู้สืบทอดสองคน ออโตมาตาต้นไม้จำกัด (ไม่แน่นอนหากเป็นแบบบนลงล่าง) เพียงพอสำหรับ WS2S ^{[ 7 ]}

โดยใช้การระบายสีเพื่อแยกแยะสมาชิกของFและQและใช้ตัวอักษรเรียงลำดับF = { false , true , nil , cons (.,.) } โดยที่consมีจำนวนอาร์กิวเมนต์ 2 และสัญลักษณ์อื่นๆ ทั้งหมดมีจำนวนอาร์กิวเมนต์ 0 ออโตมาตาต้นไม้แบบล่างขึ้นบนที่ยอมรับเซตของรายการจำกัดทั้งหมดของค่าบูลีนสามารถกำหนดได้เป็น ( Q , F , Q _f , Δ) โดยที่Q = { Bool , BList }, Q _f = { BList }และ Δ ประกอบด้วยกฎต่างๆ

เท็จ	→	บูลีน (เท็จ )	(1)
จริง	→	บูลีน (จริง )	(2)
ไม่มี	→	บลิสต์ (ไม่มี )	(3) และ
cons ( Bool (x 1 ), BList (x 2 ))	→	BList ( cons (x 1 ,x 2 ))	(4).

ในตัวอย่างนี้ กฎสามารถเข้าใจได้โดยสัญชาตญาณว่าเป็นการกำหนดประเภทให้กับแต่ละเทอมในลักษณะจากล่างขึ้นบน เช่น กฎ (4) สามารถอ่านได้ว่า "เทอมcons ( x ₁ , x ₂ ) มีประเภทBListโดยมีเงื่อนไขว่าx ₁และx ₂มีประเภทBoolและBListตามลำดับ" ตัวอย่างการทำงานที่ยอมรับได้คือ

	ข้อเสีย (	เท็จ ,	ข้อเสีย (	จริง ,	ไม่มี	))
⇒	ข้อเสีย (	เท็จ ,	ข้อเสีย (	จริง ,	บลิสต์ (ไม่มี )	))	โดย (3)
⇒	ข้อเสีย (	เท็จ ,	ข้อเสีย (	บูลีน (จริง )	บลิสต์ (ไม่มี )	))	โดย (2)
⇒	ข้อเสีย (	เท็จ ,	รายชื่อ B (ข้อเสีย (	จริง ,	ไม่มี	)))	โดย (4)
⇒	ข้อเสีย (	บูล (เท็จ )	รายชื่อ B (ข้อเสีย (	จริง ,	ไม่มี	)))	โดย (1)
⇒	รายชื่อ B (ข้อเสีย (	เท็จ ,	ข้อเสีย (	จริง ,	ไม่มี	)))	โดย (4) ยอมรับ

เปรียบเทียบกับการอนุมานคำศัพท์เดียวกันจากไวยากรณ์ต้นไม้ปกติที่สอดคล้องกับออโตมาตอน ซึ่งแสดงไว้ในไวยากรณ์ต้นไม้ปกติ#ตัวอย่าง

ตัวอย่างการปฏิเสธการทำงานคือ

	ข้อเสีย (	เท็จ ,	จริง	)
⇒	ข้อเสีย (	เท็จ ,	บูลีน (จริง )	)	โดย (1)
⇒	ข้อเสีย (	บูล (เท็จ )	บูลีน (จริง )	)	โดย (2) ไม่มีกฎเพิ่มเติมที่ใช้ได้

โดยสัญชาตญาณแล้ว นี่สอดคล้องกับคำว่าcons ( false , true ) ที่ไม่ได้กำหนดประเภทไว้อย่างถูกต้อง

Using the same colorization as above, this example shows how tree automata generalize ordinary string automata. The finite deterministic string automaton shown in the picture accepts all strings of binary digits that denote a multiple of 3. Using the notions from Deterministic finite automaton#Formal definition, it is defined by:

• the set Q of states being { S₀, S₁, S₂ },
• the input alphabet being { 0, 1 },
• the initial state being S₀,
• the set of final states being { S₀ }, and
• the transitions being as shown in column (B) of the table.

In the tree automaton setting, the input alphabet is changed such that the symbols 0 and 1 are both unary, and a nullary symbol, say nil is used for tree leaves. For example, the binary string "110" in the string automaton setting corresponds to the term "1(1(0(nil)))" in the tree automaton setting; this way, strings can be generalized to trees, or terms. The top-down finite tree automaton accepting the set of all terms corresponding to multiples of 3 in binary string notation is then defined by:

• the set Q of states being still { S₀, S₁, S₂ },
• the ranked input alphabet being { 0, 1, nil }, with Arity(0)=Arity(1)=1 and Arity(nil)=0, as explained,
• โดยเซตของสถานะเริ่มต้นคือ { S ₀ } และ
• การเปลี่ยนสถานะเป็นไปตามที่แสดงในคอลัมน์ (C) ของตาราง

ตัวอย่างเช่น ต้นไม้ " 1 ( 1 ( 0 ( nil )))" ได้รับการยอมรับโดยการทำงานของออโตมาตาต้นไม้ดังต่อไปนี้:

ในทางตรงกันข้าม เทอม " 1 ( 0 ( nil ))" นำไปสู่การทำงานของออโตมาตาที่ไม่ยอมรับดังต่อไปนี้:

เนื่องจากไม่มีสถานะเริ่มต้นอื่นใดนอกจากS ₀ที่จะใช้เริ่มต้นการทำงานของออโตมาตอน ดังนั้นเทอม " 1 ( 0 ( nil ))" จึงไม่ได้รับการยอมรับจากออโตมาตอนต้นไม้

เพื่อวัตถุประสงค์ในการเปรียบเทียบ ตารางในคอลัมน์ (A) และ (D) แสดงไวยากรณ์ปกติ (สตริง)และไวยากรณ์ต้นไม้ปกติตามลำดับ โดยแต่ละไวยากรณ์ยอมรับภาษาเดียวกันกับไวยากรณ์อัตโนมัติที่เทียบเท่ากัน

สำหรับออโตมาตาแบบจากล่างขึ้นบน เทอมพื้นฐานt (นั่นคือ ต้นไม้) จะได้รับการยอมรับหากมีการลดรูปที่เริ่มต้นจากtและสิ้นสุดที่q ( t ) โดยที่qเป็นสถานะสุดท้าย สำหรับออโตมาตาแบบจากบนลงล่าง เทอมพื้นฐานtจะได้รับการยอมรับหากมีการลดรูปที่เริ่มต้นจากq ( t ) และสิ้นสุดที่tโดยที่qเป็นสถานะเริ่มต้น

ภาษาต้นไม้L ( A ) ที่ยอมรับหรือรู้จักโดยออโตมาตาต้นไม้Aคือเซตของเงื่อนไขพื้นฐานทั้งหมดที่A ยอมรับ เซตของเงื่อนไขพื้นฐานจะรู้จักได้ก็ต่อเมื่อมีออโตมาตาต้นไม้ที่ยอมรับเซตนั้น

โฮโมมอร์ฟิซึมต้นไม้เชิงเส้น (นั่นคือ รักษาจำนวนอาร์กิวเมนต์) จะรักษาความสามารถในการจดจำ^{[ 8 ]}

ออโตมาตาต้นไม้จำกัดแบบไม่กำหนดจะสมบูรณ์ก็ต่อเมื่อมีกฎการเปลี่ยนสถานะอย่างน้อยหนึ่งกฎที่ใช้ได้สำหรับทุกชุดสัญลักษณ์-สถานะที่เป็นไปได้ สถานะqสามารถเข้าถึงได้ก็ต่อเมื่อมีเทอมพื้นฐานt อยู่ เช่นนั้นจะมีการลดรูปจากtไปยังq ( t ) NFTA จะถูกลดรูปก็ต่อเมื่อสถานะทั้งหมดสามารถเข้าถึงได้^{[ 9 ]}

เทอมพื้นฐานt ที่ มีขนาดใหญ่พอสมควร^{[ 10 ]}ในภาษาต้นไม้ที่รู้จักLสามารถแบ่งออกเป็นสามส่วนในแนวตั้ง^{[ 11 ]}โดยที่การทำซ้ำโดยพลการ ("การสูบ") ของส่วนกลางจะทำให้เทอมที่ได้ยังคงอยู่ในL ^{[ 12 ] [ 13 ]}

สำหรับภาษาของลิสต์จำกัดทั้งหมดของค่าบูลีนจากตัวอย่างข้างต้น เทอมทั้งหมดที่เกินขีดจำกัดความสูงk = 2 สามารถถูกเพิ่มเข้าไปได้ เนื่องจากเทอมเหล่านั้นจำเป็นต้องมีคำว่าcons ปรากฏอยู่ ตัวอย่างเช่น

ข้อเสีย (เท็จ ,	cons ( true , nil )	)	,
ข้อเสีย (เท็จ ,ข้อเสีย (เท็จ ,	cons ( true , nil )	))	,
ข้อเสีย (เท็จ ,ข้อเสีย (เท็จ ,ข้อเสีย (เท็จ ,	cons ( true , nil )	)))	...

ทั้งหมดล้วนอยู่ในภาษานั้น

คลาสของภาษาต้นไม้ที่สามารถจดจำได้นั้นปิดภายใต้การรวม การเติมเต็ม และการตัดกัน^{[ 14 ]}

ความสอดคล้องบนเซตของต้นไม้ทั้งหมดเหนือตัวอักษรลำดับFคือความสัมพันธ์สมมูลที่u ₁ ≡ v ₁และ ... และu _n ≡ v _nหมายความว่าf ( u ₁ ,..., u _n ) ≡ f ( v ₁ ,..., v _n )สำหรับทุกf ∈ Fความสัมพันธ์นี้จะมีดัชนีจำกัดหากจำนวนชั้นสมมูลของมันมีจำกัด

สำหรับภาษาต้นไม้Lที่ กำหนดให้ ความสอดคล้องสามารถนิยามได้โดยu ≡ _L vถ้าC [ u ] ∈ L ⇔ C [ v ] ∈ Lสำหรับแต่ละบริบทC

ทฤษฎีบทMyhill–Nerodeสำหรับออโตมาตาต้นไม้ระบุว่าข้อความสามข้อความต่อไปนี้เทียบเท่ากัน: ^{[ 15 ]}

1. Lเป็นภาษาต้นไม้ที่สามารถจดจำได้
2. Lคือการรวมกันของชั้นสมมูลบางชั้นของการสมภาคที่มีดัชนีจำกัด
3. ความสัมพันธ์≡ _Lเป็นความสอดคล้องที่มีดัชนีจำกัด

ตามที่ Engelfriet กล่าว^{[ 16 ]}ออโตมาตาต้นไม้จำกัดแบบล่างขึ้นบนถูกคิดค้นขึ้นประมาณปี 1965 โดยอิสระโดย ( Doner 1965 ) ( Doner 1970 ) และ ( Thatcher & Wright 1968 ) และในเวลาต่อมาโดย ( Pair & Quere 1968 ) ออโตมาตาต้นไม้จำกัดแบบบนลงล่างได้รับการแนะนำโดย ( Rabin 1969 ) และ ( Magidor & Moran 1969 ) และไวยากรณ์ต้นไม้ปกติโดย ( Brainerd 1969 )

ในวารสารNotices of the AMS ฉบับเดือนพฤศจิกายน พ.ศ. 2508 มี บทคัดย่อสองเรื่อง ( Doner 1965 ) และ ( Thatcher & Wright 1965 ) ซึ่งทั้งสองเรื่องได้รับการส่งมาเมื่อวันที่ 17 กันยายน บทคัดย่อทั้งสองเรื่องอ้างอิงถึงกันและกัน โดยกล่าวว่าออโตมาตาต้นไม้จำกัดได้รับการค้นพบโดยอิสระ ในขณะที่ Thatcher & Wright ยอมรับว่าการประยุกต์ใช้เพื่อพิสูจน์ความสามารถในการตัดสินใจของ "ทฤษฎีลำดับที่สองแบบอ่อนของ ฟังก์ชันผู้สืบทอด kตัว" นั้น Doner เป็นผู้ค้นพบก่อน

• ทฤษฎีบทของคูร์เซลล์ - การประยุกต์ใช้เครื่องจักรสถานะต้นไม้เพื่อพิสูจน์ทฤษฎีบทเชิงอัลกอริทึมเกี่ยวกับกราฟ
• ทรานสดิวเซอร์แบบต้นไม้ - ขยายออโตมาตาแบบต้นไม้ในลักษณะเดียวกับที่ทรานสดิวเซอร์แบบคำขยายออโตมาตาแบบคำ
• ออโตมาตาต้นไม้สลับ
• ออโตมาตาต้นไม้อนันต์

• Grappa ( เก็บถาวรเมื่อวันที่ 1 กุมภาพันธ์ 2019 ที่Wayback Machine ) - ไลบรารีออโตมาตาต้นไม้แบบจัดอันดับและไม่จัดอันดับ (OCaml)
• Timbuk - เครื่องมือสำหรับการวิเคราะห์การเข้าถึงและการคำนวณออโตมาตาต้นไม้ (OCaml)
• LETHAL - ไลบรารีสำหรับทำงานกับต้นไม้จำกัดและออโตมาตาแบบเฮดจ์ (Java)
• ไลบรารีออโตมาตาต้นไม้ที่ตรวจสอบด้วยเครื่อง (Isabelle [OCaml, SML, Haskell])
• VATA - ไลบรารีสำหรับการจัดการออโตมาตาต้นไม้แบบไม่กำหนดผลลัพธ์อย่างมีประสิทธิภาพ (C++)