ماشین متناهی متغیر

در نظریهٔ محاسبه، یک ماشین متناهی متغیر، یک ماشین متناهی غیر قطعی است که انتقال‌های آن به انتقال‌های وجودی و عمومی تقسیم می‌شود. به‌طور مثال، فرض کنید A یک ماشین متغیر باشد.

برای انتقال وجودی $(q,a,q_{1}\vee q_{2})$ ،

Aبه‌طور غیر قطعی، با خواندن a تغییر به یکی از حالتهای یا را انتخاب می‌کند؛ بنابراین مانند یک ماشین غیر قطعی منظم رفتار می‌کند.

برای یک انتقال عمومی $(q,a,q_{1}\wedge q_{2})$

A به $q_{1}$ و $q_{2}$ حرکت می‌کند، در حالی که a را می‌خواند و رفتار ماشین موازی را شبیه‌سازی می‌کند.

توجه کنید که به دلیل کمی سازی سراسری، یک اجرا بوسیلهٔ درخت اجرا نمایش داده می‌شود. اگر یک درخت اجرا در w وجود داشته باشد که هر مسیر به یک حالت پذیرش ختم شود A کلمهٔ w را قبول می‌کند. یک قضیهٔ پایه‌ای می‌گوید که هر AFA با اجرای نوع مشابهی از ساختار مجموعهٔ توانی همانطور که برای انتقال از NFA به یک ماشین متناهی قطعی استفاده می‌شود، معادل یک ماشین متناهی غیر قطعی است. این ساختار، یک AFA با k وضعیت را به NFA با بیش از $2^{k}$ وضعیت تغییر می‌دهد.

یک مدل دیگر که به‌طور رایج استفاده می‌شود، آن است که ترکیبات بولی به عنوان عبارات نشان داده می‌شوند. به‌طور مثال می‌توان فرض کرد که ترکیبات دارای فرم نرمال فصلی هستند، به طوری که $\{\{q_{1}\},\{q_{2},q_{3}\}\}$ $q_{1}\vee (q_{2}\wedge q_{3})$ را نشان می‌دهد. وضعیت tt (درست) با $\{\{\}\}$ و وضعیت ff (نادرست) با $\varnothing$ نشان داده می‌شود. این نمایش عبارت معمولاً کاراتر است.

تعریف رسمی[ویرایش]

یک ماشین متناهی متغیر، ۶ تایی $(S(\exists ),S(\forall ),\Sigma ,\delta ,P_{0},F)$ است، که درآن

$S(\exists )$ یک مجموعهٔ متناهی از وضعیت‌های وجودی است. هم چنین اغلب به صورت $S(\vee )$ نشان داده می‌شود.
$S(\forall )$ مجموعه‌ای متناهی از وضعیت‌های سراسری است. هم چنین اغلب به صورت $S(\wedge )$ نشان داده می‌شود.
$\ \Sigma$ مجموعه‌ای متناهی از نمادهای ورودی است.
$\ \delta$ مجموعه‌ای از توابع انتقال به وضعیت بعدی $(S(\exists )\cup S(\forall ))\times (\Sigma \cup \{\varepsilon \})\to 2^{S(\exists )\cup S(\forall )}$
$\ P_{0}$ . وضعیت آغازین است، به طوری که $P_{0}\in S(\exists )\cup S(\forall )$ .
$\ F$ مجموعه‌ای از وضعیت‌های پذیرش است، به طوری که $F\subseteq S(\exists )\cup S(\forall )$ .