در نظریه اتوماتا، ماشین تعیین ناپذیر با ε حرکت(NFA-ε)، حالت توسعه یافته اتوماتون تعین ناپذیر متناهی (NFA) است، به طوری که بدون مصرف هیچ حرف ورودی، می تواند به حالت جدیدی تبدیل شود. انتقال، بدون مصرف هیچ گونه نماد ورودی را ε-گذارمی نامند.
Q {\displaystyle Q\!} یک مجموعهٔ متناهی از حالات
Σ {\displaystyle \Sigma \!} یک مجموعهٔ متناهی از نمادهای ورودی موسوم به الفبا
q 0 {\displaystyle q_{0}\!} حالت آغازین (q0 ∈ Q)
F {\displaystyle F\!} مجموعهٔ حالات نهائی یا مجموعهٔ حالات مورد قبول (F ⊆ Q)
δ {\displaystyle \delta \!} تابع انتقال ((δ:Q × (Σ ∪{ε}) → P(Q)
ε-گذار، یک راه حل مناسب، برای طراحی سیستم هایی را فراهم می کند که تا به حال، حالتهایاین سیستم ها دقیقاً شناخته نشده است.ε-گذار هیچ ظرفیت بیشتری برای تفهیم زبان صوری ندارد. NFA و NFA-ε هر دو برای تفهیم یک موضوع از زبان صوری هستند، موضوعی به نام زبان منظم.NFA-ε را تعریف می کنیم چون اثبات برخی خواص بر روی آن ها نسیت بهNFA آسان تر است. از آنجا که یک NFA-ε همیشه می تواند به NFA تبدیل شود پس تمام ویژگی ها نیز برای NFA صدق است.
به طور مثال فرض کنید NFA-ε شامل دو حالت ۱ و ۲ است و می تواند بدون مصرف هیچ نمادی از رشته ورودی به حالت۲ رود. اگر در حالت ۱ باشد، و نماد ورودی بعدی a باشد، ابهامی وجود دارد: آیا این سیستم قبل از استفاده از نماد a در حالت ۱ است یا حالت ۲؟به خاطر این ابهام، بهتر است از مجموعهٔ حالتهای ممکن بگوییم که ممکن است وارد سیستم بشود. بنابراین، قبل از مصرف نماد a، این ماشین می تواند در هر یک از حالتهای مجموعه {1و ۲} باشد. معادلاً می توان تصور کرد که NFA همزمان در حالت ۱و ۲ است و این اشاره غیر مستقیمی powerset construction دارد که معادل ترجمه NFA به DFA است.
NFA-ε به یک پنج تائی M = ( Q , Σ , δ , q 0 , F ) {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)\!} گفته می شود، که شامل:
Q {\displaystyle Q\!} یک مجموعهٔ متناهی از حالات
Σ {\displaystyle \Sigma \!} یک مجموعهٔ متناهی از نمادهای ورودی موسوم به الفبا
q 0 {\displaystyle q_{0}\!} حالت آغازین (q0 ∈ Q)
F {\displaystyle F\!} مجموعهٔ حالات نهائی یا مجموعهٔ حالات مورد قبول (F ⊆ Q)
δ {\displaystyle \delta \!} تابع انتقال ((δ:Q × (Σ ∪{ε}) → P(Q)
ε-گذار، یک راه حل مناسب، برای طراحی سیستم هایی را فراهم می کند که تا به حال، حالتهایاین سیستم ها دقیقاً شناخته نشده است.ε-گذار هیچ ظرفیت بیشتری برای تفهیم زبان صوری ندارد. NFA و NFA-ε هر دو برای تفهیم یک موضوع از زبان صوری هستند، موضوعی به نام زبان منظم.NFA-ε را تعریف می کنیم چون اثبات برخی خواص بر روی آن ها نسیت بهNFA آسان تر است. از آنجا که یک NFA-ε همیشه می تواند به NFA تبدیل شود پس تمام ویژگی ها نیز برای NFA صدق است.
به طور مثال فرض کنید NFA-ε شامل دو حالت ۱ و ۲ است و می تواند بدون مصرف هیچ نمادی از رشته ورودی به حالت۲ رود. اگر در حالت ۱ باشد، و نماد ورودی بعدی a باشد، ابهامی وجود دارد: آیا این سیستم قبل از استفاده از نماد a در حالت ۱ است یا حالت ۲؟به خاطر این ابهام، بهتر است از مجموعهٔ حالتهای ممکن بگوییم که ممکن است وارد سیستم بشود. بنابراین، قبل از مصرف نماد a، این ماشین می تواند در هر یک از حالتهای مجموعه {1و ۲} باشد. معادلاً می توان تصور کرد که NFA همزمان در حالت ۱و ۲ است و این اشاره غیر مستقیمی powerset construction دارد که معادل ترجمه NFA به DFA است.
NFA-ε به یک پنج تائی M = ( Q , Σ , δ , q 0 , F ) {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)\!} گفته می شود، که شامل: