ماشین درختی

ماشین های خودکار درختی یکی از انواع ماشین های حالت است که به جای رشته های بیشتر ماشین های قراردادی، با درخت تجزیه (ساختار درختی) سروکار دارد.
Wikipedia contributors, "Tree automaton," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Tree_automaton&oldid=625685926 (accessed January 21, 2015).
مقاله پیش رو به دستورهای شاخه ای ماشین درختی می پردازد که به زبان های منظم درخت مربوط می شود. برای درک متفاوتی ماشین درختی می توانید ماشین های درختی متحرک را ببینید.
همانند ماشین های کلاسیک، ماشین های درختی متناهی (FTA) نیز، می توانند جزء ماشین های قطعی باشند یا نباشند. بر اساس چگونگی پردازش ورودی های درخت توسط ماشین، ماشین های درخت متناهی به دو دسته تقسیم می شوند: الف) پایین به بالا و ب) بالا به پایین. این مسئله بسیار حائز اهمیت است علی رغم این که ماشین های غیرقطعی هر دو نوع در قدرت بیانی معادل هم هستند، ماشین های قطعی نوع پایین به بالا به طور جدی از قدرت کمتری نسبت به ماشین های قطعی نوع مقابل برخوردار هستند. زیرا ویژگی های درخت که با ماشین های قطعی پایین به بالا مشخص می شوند، فقط می توانند به ویژگی های مسیر وابسته باشند. (ماشین های پایین به بالای قطعی به قدرت ماشین های غیرقطعی می باشند)
الفبای رتبه بندی شده جفتی از الفبای معمولی F و تابع F→N است. هر حرف در F دامنه خودش را دارد و می تواند یک جمله بسازد. جملات ساخته شده با نمادهای ثابت و یکتا می توانند به عنوان یک رشته در نظر گرفته شوند. دامنه های بیشتر می توانند منجر به ساخت درخت های بهتری می شوند.