ماشین درختی

ماشین‌های خودکار درختی یکی از انواع ماشین‌های حالت است که به جای رشته‌های بیشتر ماشین‌های قراردادی، با درخت تجزیه (ساختار درختی) سروکار دارد.

مقاله پیش رو به دستورهای شاخه‌ای ماشین درختی می‌پردازد که به زبان‌های منظم درخت مربوط می‌شود. برای درک متفاوتی ماشین درختی می‌توانید ماشین‌های درختی متحرک را ببینید.

همانند ماشین‌های کلاسیک، ماشین‌های درختی متناهی (FTA) نیز، می‌توانند جزء ماشین‌های قطعی باشند یا نباشند. بر اساس چگونگی پردازش ورودی‌های درخت توسط ماشین، ماشین‌های درخت متناهی به دو دسته تقسیم می‌شوند: الف) پایین به بالا و ب) بالا به پایین. این مسئله بسیار حائز اهمیت است علی‌رغم این که ماشین‌های غیرقطعی هر دو نوع در قدرت بیانی معادل هم هستند، ماشین‌های قطعی نوع پایین به بالا به‌طور جدی از قدرت کمتری نسبت به ماشین‌های قطعی نوع مقابل برخوردار هستند. زیرا ویژگی‌های درخت که با ماشین‌های قطعی پایین‌به‌بالا مشخص می‌شوند، فقط می‌توانند به ویژگی‌های مسیر وابسته باشند. (ماشین‌های پایین‌به‌بالای قطعی به قدرت ماشین‌های غیرقطعی می‌باشند)

تعریف

الفبای رتبه‌بندی‌شده جفتی از الفبای معمولی F و تابع F→N است. هر حرف در F دامنه خودش را دارد و می‌تواند یک جمله بسازد. جملات ساخته شده با نمادهای ثابت و یکتا می‌توانند به عنوان یک رشته در نظر گرفته شوند. دامنه‌های بیشتر می‌توانند منجر به ساخت درخت‌های بهتری می‌شوند.

ماشین‌های درختی متناهی پایین‌به‌بالا روی F، یک چندتایی (Q, F, Q_f, Δ) محسوب می‌شوند که در آن Q مجموعه حروفی است که برای بیان حالت به کار می‌روند؛ F الفبای رتبه‌بندی است و Q_f ⊆ Q مجموعه‌ای از حالت‌های نهایی است و Δ مجموعه‌ای از قوانین حالت‌گذار برای توابع ((f(q₁(x₁),...,q_n(x_n))→q(f(x₁,...,x_n می‌باشد. برای هر f عضو F، q_1 و q_iعضو Q و متغیرهای X_i که زیر درخت‌ها را تفکیک می‌کنند. اعضای مجموعه Δ قوانین بازنویسی از گره‌هایی که ریشه داده‌های آن حالات هستند تا گره‌هایی می‌باشد که ریشه‌های آن‌ها حالتشان است؛ بنابراین حالت یک گره از داده‌های آن‌ها مشخص می‌شود.

برای n=۰، که یک ثابت برای f می‌باشد، تعریف قانون‌گذار بالا به این صورت خوانده می‌شود: (()f() → q(f و گاهی پرانتزهای خالی برای راحتی نوشته نمی‌شوند: (f → q(f. از آن‌جا که این قوانین‌گذار برای ثابت‌ها (برگ‌ها)، نیاز به حالت ندارند، هیچ اولیه‌ای برای تعریف واضح‌تر آن‌ها نیاز نیست. یک ماشین خودکار درختی بر روی جمله پایه‌ای از F اجرا می‌شود که از برگ‌ها شروع شده و نسبت به حالت اجرا از Q در هر زیرجمله، به سمت بالا حرکت می‌کند. یک درخت زمانی پذیرفته می‌شود که ریشه‌های آن مرتبط با حالتی پذیرفته از Q_f باشند.

یک ماشین درختی متناهی بالابه‌پایین بر روی F نیز یک چندتایی (Q, F, Q_i, Δ) محسوب می‌شود که با ماشین‌های پایین‌به‌بالا دو تفاوت دارد. اول این‌که، Q_i ⊆ Q به عنوان مجموعه حالت‌های اولیه، به جای Q_f می‌نشیند. دوم اینکه، قوانین‌گذار مربوط به آن بالعکس تعریف می‌شوند: ((q(f(x₁,... ,x_n)) → f(q₁(x₁),... ,q_n(x_n، برای هر f عضو F و q_i عضو Q و متغیرهای X_i که زیر درخت‌ها را تفکیک می‌کنند. اعضای مجموعه Δ قوانین بازنویسی از گره‌هایی که ریشه‌های آن حالت هستند تا گره‌هایی که ریشه داده‌های آن، حالت هستند. یک ماشین بالابه‌پایین از ریشه شروع می‌شود و در طول شاخه‌های درخت به نسبت حالت اجرا در هر زیر جمله به سمت پایین حرکت می‌کند و در این‌حالت زمانی یک درخت پذیرفته‌است که تمام شاخه‌های آن از این طریق بتوانند حرکت کنند.

یک ماشین پایین‌به‌بالا، به نام ماشین قطعی (به اختصار DFTA) نامیده می‌شود اگر هیچ دو قانونی از Δ سمت چپ یکسانی نداشته باشند و در غیر اینصورت غیر قطعی (به اختصار NDFTA) نامیده می‌شود. ماشین‌های درختی بالابه‌پایین غیرقطعی نسبت به ماشین‌های پایین‌به‌بالای غیرقطعی، قدرت بیانی یکسانی دارند؛ قوانین‌گذار به سادگی معکوس می‌شود و حالت‌های نهایی، تبدیل به اولین حالات می‌شوند.

در مقایسه، ماشین‌های درختی بالابه‌پایین قطعی، نسبت به ماشین‌های پایین‌به‌بالای قطعی قدرت بیانی کمتری دارند به دلیل این‌که در ماشین‌های قطعی هیچ دو قانون‌گذاری سمت چپ یکسان ندارد.

در ماشین‌های درختی قوانین‌گذار همان قوانین بازنویسی هستند و برای انواع ماشین‌های بالابه‌پایین، سمت چپ گره‌های اصلی خواهند بود. در نتیجه، ماشین‌های بالابه‌پایین قطعی فقط برای امتحان مشخصات درختی قابل اجرا هستند که تمام شاخه‌های آن درست باشد؛ چرا که انتخاب حالتی برای نوشتن شاخه‌های کودک بدون آگاهی از محتوای شاخه‌ها، در گره‌های اصلی تعیین می‌شود.

مثال‌ها

بکارگیری رنگ‌ها برای تشخیص اعضای Q و F و استفاده از الفبای رتبه‌بندی{غلط، درست، صفر، مثبت(. ,.)} برای تشخیص یک ماشین پایین‌به‌بالا، مجموعه‌ای از تمام مقادیر متناهی عملگرهای منطقی بولی، می‌توانند با (Q, F, Q_f, Δ) تعریف شوند. با مقدار {Q={ Bool,BList }, Q_f={ BList و Δ که شامل قوانین زیر می‌شود:

false → Bool(false) (۱،

true → Bool(true) (۲،

nil → BList(nil) (۳،

cons(Bool(x1),BList(x2)) → BList(cons(x1,x2)) (۴.

False: غلط- True: درست - Nil: صفر-Cons: مثبت

یک مثال از اجرای قابل‌قبول به صورت زیر است: (cons(false, cons(true, nil

⇒ cons(false, cons(true, BList(nil))) by (3

⇒ cons(false, cons(Bool(true), BList(nil))) by (2

⇒ cons(false, BList(cons(true, nil))) by (4

⇒ cons(Bool(false), BList(cons(true, nil))) by (1

⇒ BList(cons(false, cons(true, nil))) by (4,

و مثالی از اجرای غیرقابل قبل:

(cons(false, true

⇒ cons(false, Bool(true)) by (1

⇒ cons(Bool(false), Bool(true)) by (2,

مشخصات

شناسایی

برای یک ماشین پایین‌به‌بالا، جمله پایه t (که یک درخت است) قابل قبول است اگر کاهشی وجود داشته باشد که از t شروع شده و به (q(t جایی که حالت آخر است، ختم شود. برای یک ماشین از بالابه‌پایین، جمله پایه t قابل قبول است اگر کاهشی وجود داشته باشد که از (q(t شروع شده و به t جایی که حالت اولیه است، ختم شود.

زبان درخت (L(A که به وسیله ماشین A شناخته می‌شود، مجوعه‌ای از تمام جملات پایه‌ای است که A آن‌ها را می‌پذیرد؛ بنابراین مجموعه جملات پایه در صورتی شناخته می‌شوند که ماشین A آن‌ها را بشناسد؛ و یک همومورف خطی این توان شناخت را حفظ می‌کند.

تکامل و کاهش

یک ماشین متناهی غیرقطعی زمانی کامل است که حداقل یک قانون‌گذار برای هر ترکیب احتمالی حالات وجود داشته باشد و حالت q دستیابی‌پذیر است اگر جمله پایه t که کاهش از t به (q(t منجر می‌شود، وجود داشته باشد و در نهایت یک ماشین خودکار غیرقطعی زمانی قابل پذیرش است که همه حالت‌های آن قابل دستیابی باشند.

لم تزریق

هر جمله پایه t که به حدکافی بلند باشد، در زبان درخت قابل شناسایی L، می‌تواند به‌طور افقی به سه جزء تقسیم شود به‌طوری‌که هر تکرار دلخواهی در قسمت‌های میانی، سبب می‌شود جواب در همان جمله L بماند. برای زبان تمام مقادیر متناهی بولی از مثال‌های بالا، تمام جملات با محدودیت بلندی بیشتر از ۲ بودن، می‌توانند تزریق شوند. برای مثال:

((cons(false, cons(true,nil ,

(((cons(false,cons(false, cons(true,nil ,

((((cons(false,cons(false,cons(false, cons(true,nil , ...

قضیه Myhill-Nerode

تناسب روی زبان‌های درخت، یک نسبت هم ارز می‌باشد برای مثال: u₁ ≡ v₁و... و u_n ≡ v_n، بر رابطه هم ارز زیر دلالت می‌کند:

(f(u₁,... ,u_n) ≡ f(v₁,... ,v_n

برای زبان درخت داده شده، این نسبت می‌تواند به صورت u ≡_L v نشان داده شود اگر C[u] ∈ L ⇔ C[v] ∈ L برقرار باشد. این قضیه بیان می‌کند که:

1. L در هر زبان درخت قابل شناسایی است.
2. L اجتماعی از تمام دسته‌های هم ارز شاخص‌های متناهی است.
3. رابطه _L≡، یک شاخص متناهی هم ارز است.

منابع

• Wikipedia contributors, "Tree automaton," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Tree_automaton&oldid=625685926 (accessed January 21, 2015).