درخت رونده اتوماتا

یک درخت رونده اتوماتا یک نوع اتوماتا متناهی است که به جای رشته‌ها درخت‌ها را تحلیل می‌کند. این مفهوم توسط Aho و Ullman پیشنهاد شده‌است.

این درخت بسیار شبیه درخت گرامر درخت منظم و ماشین درختی به عبارتی می‌توان گفت این درخت نمایشی متفاوت از دو درخت یاد شده‌است.

تعریف

تمام درخت‌های به این شکل دودویی هستند و دارای برچسب‌هایی با الفبای ثابت هستند در واقعیت این درخت‌ها دارای تعدادی حالت هستند که با آمدن حروف جدید مانند اتومات‌های واقعی از حالتی به حالت دیگر حرکت می‌کند و در نهایت اگر در حالت تأیید به کار خود پایان داد که آن درخت تأیید می‌شود و اگر در حالت رد یا حلقهٔ بی‌نهایت به کار خود پایان داد آن درخت رد می‌شود.

اگر بخواهیم به صورت ریاضی تر آن را بگوییم هر درخت غیر قطعی رونده اتوماتا یک شش‌تایی A = (Q, Σ, I, F, R, δ) است که Σ الفبایی ثابت بوده، Q مجموعهٔ حالت‌ها ،I حالت‌های شروع، F حالت‌های تأیید و R حالت‌های رد است. همان‌طور که در تمامی اتومات‌ها رابطه‌هایی وجود دارد که با دیدن یک حرف از حالی به حالت دیگر می‌رود. δ ⊆ (Q × { root, left, right, leaf } × Σ × { up, left, right } × Q) Q اول به معنای حالت فعلی است که در حالت فعلی یکی از چهار حالت مشخص شده را داریم. منظور از Σ حرف دیده شده‌است و مورد بعدی به معنای حرکتی است که می‌کنیم که یکی از بالا، راست و چب است و Q آخر نیز به معنای حالتی است که در آن می‌رویم. پس رابطه‌های به صورت ۵ تایی‌هایی درین اتوماتا نمایان می‌شوند.

مثال

یک مثال ساده از این درخت برای اجرا کردن الگوریتم جستجوی عمق اول بر روی درخت ورودی است. طبعاً برای هر مثال باید پارامترهای تعریف را مشخص کنیم. این اتومات‌های ۳ حالت دارد، $Q=\{q_0,q_{𝑙𝑒𝑓𝑡},q_{𝑟𝑖𝑔ℎ𝑡}\}$. در ابتدا از ریشه که حالت ۰ است شروع می‌کنیم. حال با آمدن هر راس جدید به حالت چپ وارد می‌شویم و در صورتی که در برگ درخت باشیم به بالا می‌رویم که متناظر با همان حرکت بالا بود که در تعریف از آن یاد کرده بودیم. همان‌طور که گفتیم درین درخت می‌توان مشخص کرد که آیا زیر درختی پردازش شده‌است یا نه در این‌جا هم هر جا که زیر درخت سمت چپ پردازش شده باشد باید به حالت سمت راست برویم.$A$

خواص

بر خلاف ماشین درختی، درخت رونده اتوماتا به سختی قابل تجزیه و تحلیل است و حتی خواص سادهٔ آن نیز به سختی اثبات می‌شود و بعضاً اثبات‌های بسیار پیچیده و غیر بدیهی دارند.

درین به برخی از خواص آن که اثبات شده‌است اشاره می‌کنیم

• توسط Bojańczyk و Colcombet ثابت شده‌است که درخت قطعی رونده اتوماتا زیر مجموعهٔ درخت روندهٔ اتوماتا است.${\displaystyle }$
• درخت قطعی رونده اتوماتا تحت عمل متمم‌گیری بسته‌است اما هنوز مشخص نیست که درخت‌های غیرقطعی آن نیز تحت عمل متمم گیری بسته باشند
• مجموعه ای از زبان‌هایی که توسط این درخت تشخیص داده می‌شود زیرمجموعه درخت‌های زبان منظم هستند.