اتوماتون تعیین‌ناپذیر متناهی

در تئوری محاسبات، اتوماتون تعیین‌ناپذیر متناهی یا اتوماتون غیرقابل تعیین متناهی یا یا ان‌اف‌اِی (Nondeterministic finite automaton - NFA) به اوتوماتون‌هایی گفته می‌شود که در مورد آن‌ها برای برخی از دوتایی‌های حالت و سمبل ورودی امکان عبور به بیشتر از یک حالت جدید اجازه داده شده باشد.

NFA در بعضی موارد با نام Subshift of finite type شناخته می‌شود.NFA به راه‌های متعددی , تعمیم داده شده‌است:اتومات تعین ناپذیر با ε حرکت , اتوماتون پشته‌ای ,اتومات ω ای،اتومات احتمالی.

تعریف غیررسمی

یک NFA , مانند DFA به رشته‌ای از نمادها برای ورود نیازمند است. برای هر نماد ورودی، NFA به حالتی جدیدی میرود تا بتواند تمام ورودی جدید را استفاده کند. برخلاف NFA ,DFA غیر قطعی است و برای هر نماد ورودی , حالتی بعدی می‌تواند هر کدام از چندین حالت ممکن باشد , بنابراین در تعریف رسمی حالت بعدی عضوی از مجموعه توانی از وضیعت هاست که در یک زمان در نظر گرفته می‌شود. مفهوم پذیرفتن یک ورودی در NFA به مانند DFA است. DFA زمانی پذیرفته می‌شود اگر و تنها اگر که آخرین نماد ورودی استفاده شده ِهنوز تعدادی انتقال باشد که به حالت مورد انتظار و مورد قبول برسیم. معادلاَ زمانی به  رد می‌شود  که بدون توجه به آنچه انتقال پیدا کرده‌است , به حالت مورد قبول نرسیم.

انواع NFA

ماشین‌های تعین‌پذیر حالات متناهی DFA : به آن‌دسته از ماشین‌های حالات متناهی اطلاق می‌شود که در آن‌ها به ازاء هر دوتائی شامل حالت و ورودی یک و فقط یک امکان برای عبور به حالت بعدی وجود داشته باشد.
ماشین تعیین ناپذیر با ε حرکت:این اتومات‌ها می‌توانند رابطه انتقال را تغییر دهند و به این شکل دربیاورند:(Δ : Q × (Σ ∪{ε}) → P(Q

شباهت با DFA

به ازای هر DFA , NFA وجود دارد که دارای زبان صوری یکسان‌اند.DFA را می‌توان به کمک ساختمان پاورست ساخت. و همچنین مهم است که بتوان ساختارهای NFAها را به ساختار DFAهایی با کیفیت تر تبدیل کرد. البته ممکن است که اگر یک NFA دارای n وضیعت باشد آنگاه ساختار DFA دارای ۲ⁿ وضیعت باشد که این عدد نمادی در بعضی موارد در مقادیر بزرگ می‌تواند مشکل ساز باشد.

خواص و ویژگی‌ها

ماشین با یک وضیعت اولیه کار خودش شروع می‌کند و رشته‌ای از نمادها را دریافت می‌کند. اتوماتا حالت اولیه را توسط ماشین‌های حالات متناهی  Δ به حالت جدید تبدیل می‌کنند. توجه کنیم که وضیعت NFA تنها به حالت حاضر بستگی ندارد بلکه به ورودی‌های بعدی نیز ریط دارد. تا زمانی که تمام ورودی‌های بعدی اتفاق نیفتند غیرممکن است که وضیعت ماشین را متوجه شویم. زمانی که NFA دریافت ورودی را تمام کرد آنگاه درمرحله پذیرش است و اعلام می‌کند رشته پذیرفته شدهاست در غیر این صورت رشته را رد می‌کند.
به رشته‌هایی که NFA آن را میپذیرند یک زبان مورد پذیرش NFA گویند. این زبان ,زبان منظم
است.

اجرا

راه‌های بسیاری برای اجرا NFA وجود دارد که برخی از آن‌ها عبارتند از :
۱- آن را به DFA معادل تبدیل می‌کنیم. در برخی موارد این کار سبب افزایش تصاعدی حجم ماشین و بنابراین به وجود آمدن فضاهای کمکی متناسب با تعداد حالت‌های NFA می‌شود(برای نگهداری مقدار حالت برای هر حالت در NFA حداکٹر به یک بیت حافظه نیاز است)
۲-یک ساختمان داده برای تمام حالاتی که ماشین ممکن است در حال حاضر در آن باشد نگهداری کنیم. در مصرف آخرین ورودی که ماشین می‌گیرد، اگر یکی از این حالت‌ها حالت نهایی باشد آن رشته را ماشین می پذیرد. اگر برای هر حالت NFA یک بیت هزینه شود همانند روش قبلی در بدترین حالت زمان گرفته می‌شود.

کارایی NFA

DFA و NFA از این نظر به هم شباهت دارند که اگر NFA توسط زبانی شناخته شوند , DFA نیز توسط آن زبان شناخته می‌شود. که توجه به این خاصیت مهم و مفید است. مفید است زیرا ساختن یک NFA از یک زبان راحت‌تر از ساختن DFA از آن زبان است. و از این نظر اهمیت دارد که NFA می‌تواند پیچیدگی بسیار از مسائل را که درنظریه محاسبات را کاهش دهد. به‌طور مثال اثبات closure properties از زبان منظم به وسیله NFA ساده‌تر از DFA است.