نمایش مبدأ برای ماشین متناهی متغیر

در [[نظریه اتوماتا|نظریهٔ محاسبه]]، یک '''ماشین متناهی متغیر'''، یک [[اتوماتون تعیین‌ناپذیر متناهی|ماشین متناهی غیر قطعی]] است که انتقال‌های آن به انتقال‌های [[سور وجودی|وجودی]] و [[سور عمومی|عمومی]] تقسیم می‌شود. به‌طور مثال، فرض کنید A یک ماشین متغیر باشد.
* برای انتقال وجودی <math>(q, a, q_1 \vee q_2)</math>،
''A''به‌طور غیر قطعی، با خواندن a تغییر به یکی از حالتهای یا را انتخاب می‌کند؛ بنابراین مانند یک [[اتوماتون تعیین‌ناپذیر متناهی|ماشین غیر قطعی]] منظم رفتار می‌کند.
* برای یک انتقال عمومی <math>(q, a, q_1 \wedge q_2)</math>
''A''
به
<math>q_1</math>
'''و'''
<math>q_2</math>
حرکت می‌کند، در حالی که a را می‌خواند و رفتار ماشین موازی را شبیه‌سازی می‌کند.

توجه کنید که به دلیل کمی سازی سراسری، یک اجرا بوسیلهٔ درخت اجرا نمایش داده می‌شود. اگر یک درخت اجرا در ''w'' وجود داشته باشد که هر مسیر به یک حالت پذیرش ختم شود ''A'' کلمهٔ ''w'' را قبول می‌کند.
یک قضیهٔ پایه‌ای می‌گوید که هر AFA با اجرای نوع مشابهی از ساختار [[مجموعهٔ توانی]] همانطور که برای انتقال از NFA به یک [[ماشین تعیین‌پذیر حالات متناهی|ماشین متناهی قطعی]] استفاده می‌شود، معادل یک ماشین [[اتوماتون تعیین‌ناپذیر متناهی|متناهی غیر قطعی]] است. این ساختار، یک AFA با ''k'' وضعیت را به NFA با بیش از
<math>2^k</math>
وضعیت تغییر می‌دهد.

یک مدل دیگر که به‌طور رایج استفاده می‌شود، آن است که ترکیبات بولی به عنوان عبارات نشان داده می‌شوند. به‌طور مثال می‌توان فرض کرد که ترکیبات دارای [[فرم نرمال فصلی]] هستند، به طوری که
<math>\{\{q_1\},\{q_2,q_3\}\}</math>
<math>q_1 \vee (q_2 \wedge q_3)</math>
را نشان می‌دهد. وضعیت
'''tt'''
(درست) با
<math>\{\{\}\}</math>
و وضعیت
'''ff'''
(نادرست) با
<math>\varnothing</math>
نشان داده می‌شود. این نمایش عبارت معمولاً کاراتر است.

== تعریف رسمی ==
یک ماشین متناهی متغیر، ۶ تایی <math>(S(\exists), S(\forall), \Sigma, \delta, P_0, F)</math> است، که درآن
* <math>S(\exists)</math> یک [[مجموعهٔ متناهی]] از وضعیت‌های وجودی است. هم چنین اغلب به صورت <math>S(\vee)</math> نشان داده می‌شود.
* <math>S(\forall)</math> مجموعه‌ای متناهی از وضعیت‌های سراسری است. هم چنین اغلب به صورت<math>S(\wedge)</math> نشان داده می‌شود.
* <math>\ \Sigma</math> مجموعه‌ای متناهی از نمادهای ورودی است.
* <math>\ \delta</math> مجموعه‌ای از [[تابع|توابع]] انتقال به وضعیت بعدی <math>(S(\exists) \cup S(\forall)) \times (\Sigma \cup \{ \varepsilon \}) \to 2^{S(\exists) \cup S(\forall)}</math>
* <math>\ P_0</math>. وضعیت آغازین است، به طوری که <math>P_0 \in S(\exists) \cup S(\forall)</math>.
* <math>\ F</math> مجموعه‌ای از وضعیت‌های پذیرش است، به طوری که <math>F \subseteq S(\exists) \cup S(\forall)</math>.

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* Wikipedia contributors, "Alternating finite automaton," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Alternating_finite_automaton&oldid=575677375 (accessed January 20, 2015).
{{پایان چپ‌چین}}
[[رده:ماشین متناهی]]
[[رده:نظریه اتوماتا]]


[[رده:ویکی‌سازی رباتیک]]