در نظریه اتوماتا، ماشین تعیین ناپذیر با ε حرکت[ ۱] ( NFA - ε ) ، حالت توسعه یافته اتوماتون تعین ناپذیر متناهی ( NFA ) است، به طوری که بدون مصرف هیچ حرف ورودی، می تواند به حالت[ ۲] جدیدی تبدیل شود. انتقال، بدون مصرف هیچ گونه نماد ورودی را ε - گذار[ ۳] می نامند.
ε - گذار، یک راه حل مناسب، برای طراحی سیستم هایی را فراهم می کند که تا به حال، حالتهای[ ۴] این سیستم ها دقیقاً شناخته نشده است. ε - گذار هیچ ظرفیت بیشتری برای تفهیم زبان صوری ندارد. NFA و NFA - ε هر دو برای تفهیم یک موضوع از زبان صوری هستند، موضوعی به نام زبان منظم. NFA - ε را تعریف می کنیم چون اثبات برخی خواص بر روی آن ها نسیت بهNFA آسان تر است. از آنجا که یک NFA - ε همیشه می تواند به NFA تبدیل شود پس تمام ویژگی ها نیز برای NFA صدق است.
به طور مثال فرض کنید NFA - ε شامل دو حالت ۱ و ۲ است و می تواند بدون مصرف هیچ نمادی از رشته ورودی به حالت۲ رود. اگر در حالت ۱ باشد، و نماد ورودی بعدی a باشد، ابهامی وجود دارد: آیا این سیستم قبل از استفاده از نماد a در حالت ۱ است یا حالت ۲؟به خاطر این ابهام، بهتر است از مجموعهٔ حالتهای ممکن بگوییم که ممکن است وارد سیستم بشود. بنابراین، قبل از مصرف نماد a، این ماشین می تواند در هر یک از حالتهای مجموعه {1و ۲} باشد. معادلاً می توان تصور کرد که NFA همزمان در حالت ۱و ۲ است و این اشاره غیر مستقیمی powerset construction دارد که معادل ترجمه NFA به DFA است. [ نیازمند منبع]
NFA - ε به یک پنج تائی M = ( Q , Σ , δ , 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 )
است.
فزض کنیم M یک NFA - ε است با الفبا دودویی {0، 1}، به طوریکه ورودی شامل تعداد زوج ۱ یا تعداد زوج ۰ است.
M = ( {s0, s1, s2, s3, s4}, {0, 1}, Δ, s0, {s1, s3} )
اگر زبانِ NFA - ε حاصل از اعمال عملیاتی بر NFA - εها قبل، NFA - ε شناخته شده باشد، گفته می شود که NFA - εها تحت آن عملیات بسته هستند. NFA - εها تحت عملیات زیر بسته هستند:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفε - گذار، یک راه حل مناسب، برای طراحی سیستم هایی را فراهم می کند که تا به حال، حالتهای[ ۴] این سیستم ها دقیقاً شناخته نشده است. ε - گذار هیچ ظرفیت بیشتری برای تفهیم زبان صوری ندارد. NFA و NFA - ε هر دو برای تفهیم یک موضوع از زبان صوری هستند، موضوعی به نام زبان منظم. NFA - ε را تعریف می کنیم چون اثبات برخی خواص بر روی آن ها نسیت بهNFA آسان تر است. از آنجا که یک NFA - ε همیشه می تواند به NFA تبدیل شود پس تمام ویژگی ها نیز برای NFA صدق است.
به طور مثال فرض کنید NFA - ε شامل دو حالت ۱ و ۲ است و می تواند بدون مصرف هیچ نمادی از رشته ورودی به حالت۲ رود. اگر در حالت ۱ باشد، و نماد ورودی بعدی a باشد، ابهامی وجود دارد: آیا این سیستم قبل از استفاده از نماد a در حالت ۱ است یا حالت ۲؟به خاطر این ابهام، بهتر است از مجموعهٔ حالتهای ممکن بگوییم که ممکن است وارد سیستم بشود. بنابراین، قبل از مصرف نماد a، این ماشین می تواند در هر یک از حالتهای مجموعه {1و ۲} باشد. معادلاً می توان تصور کرد که NFA همزمان در حالت ۱و ۲ است و این اشاره غیر مستقیمی powerset construction دارد که معادل ترجمه NFA به DFA است. [ نیازمند منبع]
NFA - ε به یک پنج تائی M = ( Q , Σ , δ , 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 )
است.
فزض کنیم M یک NFA - ε است با الفبا دودویی {0، 1}، به طوریکه ورودی شامل تعداد زوج ۱ یا تعداد زوج ۰ است.
M = ( {s0, s1, s2, s3, s4}, {0, 1}, Δ, s0, {s1, s3} )
اگر زبانِ NFA - ε حاصل از اعمال عملیاتی بر NFA - εها قبل، NFA - ε شناخته شده باشد، گفته می شود که NFA - εها تحت آن عملیات بسته هستند. NFA - εها تحت عملیات زیر بسته هستند:
