1265646
Ôtômat cây
https://vi.wikipedia.org/wiki?curid=1265646
Title: Ôtômat cây
Ôtômat cây (tiếng Anh: tree automaton) là một loại máy trạng thái. Ôtômat cây xử lý cấu trúc cây, thay vì xâu như các máy trạng thái thường gặp.
Bài viết này đề cập đến ôtômat phân nhánh cây, tương đương với các ngôn ngữ chính quy của cây. Một khái niệm ôtômat cây khác có thể tìm thấy là ôtômat duyệt cây. 
Tương tự ôtômat cổ điển, ôtômat cây hữu hạn có thể xác định (ÔHX) hoặc không (ÔHK). Theo cách xử lý cây đầu vào, ôtômat cây hữu hạn có thể thuộc vào hai loại: (a) dưới lên, (b) trên xuống. Đây là vấn đề quan trọng vì mặc dù ôtômat ÔHK trên xuống và ÔHK dưới lên tương đương về khả năng biểu diễn nhưng ÔHX trên xuống kém hơn hẳn ôtômat dưới lên tương ứng vì tính chất của cây xác định bởi ÔHX trên xuống chỉ có thể phụ thuộc vào tính chất của đường đi. ÔHX dưới lên mạnh ngang với ÔHK.
Định nghĩa.
Một bảng chữ cái xếp hạng là một cặp bảng chữ cái formula_1 và hàm bậc (arity) sao cho có thể xây dựng một số hạng. Các thành tố trống (bậc bằng không) còn được gọi là hằng. Toán hạng được xây dựng bằng các ký hiện bậc một và hằng có thể được coi là xâu. Bậc cao hơn tạo ra cây.
Một ôtômat cây hữu hạn trên formula_2 được định nghĩa là:
formula_3
Ở đây, formula_4 là tập các trạng thái, formula_2 là một bảng chữ cái xếp hạng formula_6 là một tập các trạng thái kết thúc và formula_7 là tập luật chuyển trạng thái, nghĩa là các luật viết lại một nút có các con là trạng thái thành nút trạng thái mới.
Không có trạng thái bắt đầu nhưng các luật chuyển cho ký hiệu hằng (nút lá) có thể được coi là các luật bắt đầu. Cây được chấp nhận nếu trạng thái ở gốc là một trạng thái chấp nhận.
Một ôtômat hữu hạn trên xuống trên formula_2 được định nghĩa bởi:
formula_9