موضوع مقاله: ماشین درختی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین درختی | مقدمه: ماشین‌های خودکار درختی یکی از انواع ماشین‌های حالت است که به جای رشته‌های بیشتر ماشین‌های قراردادی، با درخت تجزیه (ساختار درختی) سروکار دارد. | ## بخش 1: ماشین درختی | مقاله پیش رو به دستورهای شاخه‌ای ماشین درختی می‌پردازد که به زبان‌های منظم درخت مربوط می‌شود. همانند ماشین‌های کلاسیک، ماشین‌های درختی متناهی (FTA) نیز، می‌توانند جزء ماشین‌های قطعی باشند یا نباشند. بر اساس چگونگی پردازش ورودی‌های درخت توسط ماشین، ماشین‌های درخت متناهی به دو دسته تقسیم می‌شوند: الف) پایین به بالا و ب) بالا به پایین. این مسئله بسیار حائز اهمیت است علی‌رغم این که ماشین‌های غیرقطعی هر دو نوع در قدرت بیانی معادل هم هستند، ماشین‌های قطعی نوع پایین به بالا به‌طور جدی از قدرت کمتری نسبت به ماشین‌های قطعی نوع مقابل برخوردار هستند. زیرا ویژگی‌های درخت که با ماشین‌های قطعی پایین‌به‌بالا مشخص می‌شوند، فقط می‌توانند به ویژگی‌های مسیر وابسته باشند. جملات ساخته شده با نمادهای ثابت و یکتا می‌توانند به عنوان یک رشته در نظر گرفته شوند. ماشین‌های درختی متناهی پایین‌به‌بالا روی F، یک چندتایی (Q, F, Qf, Δ) محسوب می‌شوند که در آن Q مجموعه حروفی است که برای بیان حالت به کار می‌روند؛ F الفبای رتبه‌بندی است و Qf ⊆ Q مجموعه‌ای از حالت‌های نهایی است و Δ مجموعه‌ای از قوانین حالت‌گذار برای توابع f(q1(x1),...,qn(xn →q(f(x1,...,xn می‌باشد. اعضای مجموعه Δ قوانین بازنویسی از گره‌هایی که ریشه داده‌های آن حالات هستند تا گره‌هایی می‌باشد که ریشه‌های آن‌ها حالتشان است؛ بنابراین حالت یک گره از داده‌های آن‌ها مشخص می‌شود. برای n=۰، که یک ثابت برای f می‌باشد، تعریف قانون‌گذار بالا به این صورت خوانده می‌شود: f → q(f و گاهی پرانتزهای خالی برای راحتی نوشته نمی‌شوند: (f → q(f. | ## بخش 2: ماشین درختی | از آن‌جا که این قوانین‌گذار برای ثابت‌ها (برگ‌ها)، نیاز به حالت ندارند، هیچ اولیه‌ای برای تعریف واضح‌تر آن‌ها نیاز نیست. یک ماشین خودکار درختی بر روی جمله پایه‌ای از F اجرا می‌شود که از برگ‌ها شروع شده و نسبت به حالت اجرا از Q در هر زیرجمله، به سمت بالا حرکت می‌کند. یک ماشین درختی متناهی بالابه‌پایین بر روی F نیز یک چندتایی (Q, F, Qi, Δ) محسوب می‌شود که با ماشین‌های پایین‌به‌بالا دو تفاوت دارد. اعضای مجموعه Δ قوانین بازنویسی از گره‌هایی که ریشه‌های آن حالت هستند تا گره‌هایی که ریشه داده‌های آن، حالت هستند. یک ماشین بالابه‌پایین از ریشه شروع می‌شود و در طول شاخه‌های درخت به نسبت حالت اجرا در هر زیر جمله به سمت پایین حرکت می‌کند و در این‌حالت زمانی یک درخت پذیرفته‌است که تمام شاخه‌های آن از این طریق بتوانند حرکت کنند. یک ماشین پایین‌به‌بالا، به نام ماشین قطعی (به اختصار DFTA) نامیده می‌شود اگر هیچ دو قانونی از Δ سمت چپ یکسانی نداشته باشند و در غیر اینصورت غیر قطعی (به اختصار NDFTA) نامیده می‌شود. ماشین‌های درختی بالابه‌پایین غیرقطعی نسبت به ماشین‌های پایین‌به‌بالای غیرقطعی، قدرت بیانی یکسانی دارند؛ قوانین‌گذار به سادگی معکوس می‌شود و حالت‌های نهایی، تبدیل به اولین حالات می‌شوند. در مقایسه، ماشین‌های درختی بالابه‌پایین قطعی، نسبت به ماشین‌های پایین‌به‌بالای قطعی قدرت بیانی کمتری دارند به دلیل این‌که در ماشین‌های قطعی هیچ دو قانون‌گذاری سمت چپ یکسان ندارد. در ماشین‌های درختی قوانین‌گذار همان قوانین بازنویسی هستند و برای انواع ماشین‌های بالابه‌پایین، سمت چپ گره‌های اصلی خواهند بود. | ## بخش 3: ماشین درختی | در نتیجه، ماشین‌های بالابه‌پایین قطعی فقط برای امتحان مشخصات درختی قابل اجرا هستند که تمام شاخه‌های آن درست باشد؛ چرا که انتخاب حالتی برای نوشتن شاخه‌های کودک بدون آگاهی از محتوای شاخه‌ها، در گره‌های اصلی تعیین می‌شود. مثال‌ها بکارگیری رنگ‌ها برای تشخیص اعضای Q و F و استفاده از الفبای رتبه‌بندی{غلط، درست، صفر، مثبت(. برای تشخیص یک ماشین پایین‌به‌بالا، مجموعه‌ای از تمام مقادیر متناهی عملگرهای منطقی بولی، می‌توانند با (Q, F, Qf, Δ) تعریف شوند. برای یک ماشین از بالابه‌پایین، جمله پایه t قابل قبول است اگر کاهشی وجود داشته باشد که از (q(t شروع شده و به t جایی که حالت اولیه است، ختم شود. زبان درخت (L(A که به وسیله ماشین A شناخته می‌شود، مجوعه‌ای از تمام جملات پایه‌ای است که A آن‌ها را می‌پذیرد؛ بنابراین مجموعه جملات پایه در صورتی شناخته می‌شوند که ماشین A آن‌ها را بشناسد؛ و یک همومورف خطی این توان شناخت را حفظ می‌کند. تکامل و کاهش یک ماشین متناهی غیرقطعی زمانی کامل است که حداقل یک قانون‌گذار برای هر ترکیب احتمالی حالات وجود داشته باشد و حالت q دستیابی‌پذیر است اگر جمله پایه t که کاهش از t به (q(t منجر می‌شود، وجود داشته باشد و در نهایت یک ماشین خودکار غیرقطعی زمانی قابل پذیرش است که همه حالت‌های آن قابل دستیابی باشند. لم تزریق هر جمله پایه t که به حدکافی بلند باشد، در زبان درخت قابل شناسایی L، می‌تواند به‌طور افقی به سه جزء تقسیم شود به‌طوری‌که هر تکرار دلخواهی در قسمت‌های میانی، سبب می‌شود جواب در همان جمله L بماند. | ## جمع‌بندی | برای زبان تمام مقادیر متناهی بولی از مثال‌های بالا، تمام جملات با محدودیت بلندی بیشتر از ۲ بودن، می‌توانند تزریق شوند.