ماشین تعیین‌ناپذیر با ε حرکت

در نظریه اتوماتا، ماشین تعیین ناپذیر با ε حرکتNondeterministic finite automaton with ε-moves(NFA-ε)، حالت توسعه یافته اتوماتون تعین‌ناپذیر متناهی (NFA) است، به طوری که بدون مصرف هیچ حرف ورودی، می‌تواند به حالتState جدیدی تبدیل شود. انتقال، بدون مصرف هیچ گونه نماد ورودی را ε-گذارε-transitionمی‌نامند.

ε-گذار، یک راه حل مناسب، برای طراحی سیستم‌هایی را فراهم می‌کند که تا به حال، حالتهایStatesاین سیستم‌ها دقیقاً شناخته نشده‌است.ε-گذار هیچ ظرفیت بیشتری برای تفهیم زبان صوری ندارد. NFA و NFA-ε  هر دو برای تفهیم یک موضوع از زبان صوری هستند، موضوعی به نام زبان منظم.NFA-ε را تعریف می‌کنیم چون اثبات برخی خواص بر روی آن‌ها نسیت بهNFA آسان تر است. از آنجا که یک NFA-ε همیشه می‌تواند به NFA تبدیل شود پس تمام ویژگی‌ها نیز برای NFA صدق است.

 تعریف غیر رسمی 
به‌طور مثال فرض کنید NFA-ε شامل دو حالت ۱ و ۲ است و می‌تواند بدون مصرف هیچ نمادی از رشته ورودی به حالت۲ رود. اگر در حالت ۱ باشد، و نماد ورودی بعدی a باشد، ابهامی وجود دارد: آیا این سیستم  قبل از استفاده از نماد a در حالت ۱ است یا حالت ۲؟به خاطر این ابهام، بهتر است از مجموعهٔ  حالتهای ممکن بگوییم که ممکن است وارد سیستم بشود. بنابراین، قبل از مصرف نماد a، این ماشین می‌تواند در هر یک از حالتهای مجموعه {1و ۲} باشد. معادلاً می‌توان تصور کرد که NFA همزمان در حالت ۱و ۲ است و این اشاره غیر مستقیمی powerset construction دارد که معادل ترجمه NFA به DFA است.

 تعریف رسمی 
NFA-ε به یک پنج‌تائی  گفته می‌شود، که شامل:
  یک مجموعهٔ متناهی از حالات
  یک مجموعهٔ متناهی از نمادهای ورودی موسوم به الفبا
  حالت آغازین (q0 ∈ Q)
  مجموعهٔ حالات نهائی یا مجموعهٔ حالات مورد قبول (F ⊆ Q)
  تابع انتقال ((δ:Q × (Σ ∪{ε}) → P(Q)
است.

 مثال 
بندانگشتی|250px| نمودار حالتها M
فزض کنیم M یک NFA-ε است با الفبا دودویی {0،1}، به طوریکه ورودی شامل تعداد زوج ۱ یا تعداد زوج ۰  است.M = ({s0, s1, s2, s3, s4}, {0, 1}, Δ, s0, {s1, s''3})
01εS0{}{}{S1, S3}S1{S2}{S1}{}S2{S1}{S2}{}S3{S3}{S4}{}S4{S4}{S3}{}

 هم ارزی با DFA و NFA 
 ویژگی‌های بستاری 
اگر زبانِ NFA-ε حاصل از اعمال عملیاتی بر NFA-εها قبل، NFA-ε شناخته شده باشد، گفته می‌شود که  NFA-εها تحت آن عملیات بسته هستند.  NFA-εها تحت عملیات زیر بسته هستند:
 اجتماعunion
 اشتراکIntersection
 الحاقConcatenation
 ستاره کلین
 Negation

 منابع 

 پیوند به بیرون 
 http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves

رده:نظریه اتوماتا