اتوماتون تعیین‌ناپذیر متناهی
در تئوری محاسبات، اتوماتون تعیین‌ناپذیر متناهی یا اتوماتون غیرقابل تعیین متناهی یا یا ان‌اف‌اِی (Nondeterministic finite automaton - NFA) به اوتوماتون‌هایی گفته می‌شود که در مورد آن‌ها برای برخی از دوتایی‌های حالت و سمبل ورودی امکان عبور به بیشتر از یک حالت جدید اجازه داده شده باشد.
NFA در بعضی موارد با نام Subshift of finite type شناخته می‌شود.NFA به راه‌های متعددی , تعمیم داده شده‌است:اتومات تعین ناپذیر با ε حرکت , اتوماتون پشته‌ای ,اتومات ω ای،اتومات احتمالی.
یک NFA , مانند DFA به رشته‌ای از نمادها برای ورود نیازمند است. برای هر نماد ورودی، NFA به حالتی جدیدی میرود تا بتواند تمام ورودی جدید را استفاده کند. برخلاف NFA ,DFA غیر قطعی است و برای هر نماد ورودی , حالتی بعدی می‌تواند هر کدام از چندین حالت ممکن باشد , بنابراین در تعریف رسمی حالت بعدی عضوی از مجموعه توانی از وضیعت هاست که در یک زمان در نظر گرفته می‌شود. مفهوم پذیرفتن یک ورودی در NFA به مانند DFA است. DFA زمانی پذیرفته می‌شود اگر و تنها اگر که آخرین نماد ورودی استفاده شده ِهنوز تعدادی انتقال باشد که به حالت مورد انتظار و مورد قبول برسیم. معادلاَ زمانی به " رد می‌شود " که بدون توجه به آنچه انتقال پیدا کرده‌است , به حالت مورد قبول نرسیم. یک NFA به‌طور معمول با ۵ عامل معرفی می‌کنیم:("Q", Σ, Δ, "q", "F") که در آن:
حال توجه کنید که منظور از ("P"("Q" مجموعه توانی از Q است. فرض کنید که "w = aa ... a" مجموعه ورودی باشد(Σ). اتومات به شرطی دنباله w را میپذیرد که شرایط زیر را داشته باشد:
به عبارت دیگر , شرط اول می‌گوید که ماشین با q شروع به کار می‌کند.شرط دوم می‌گوید که ماشین هر کاراکتر رشته w را از حالت خود به حالت تابع Δ انتقال می‌دهد. و شرط سوم می‌گوید که ماشین زمانی w میپذیرد که آخرین ورودی w در یکی از حالات مورد قبول ماشین باعث توقف شود. در غیر اینصورت اتومات رشته ورودی را رد می‌کند. مجموعه‌ای از رشته‌هایی که پذیرفته می‌شوند را با زبان صوری M نشان میدهیم و برای نشان دادن این زبان از"(L(M" استفاده می‌کنیم.
همچنین می‌توان(L(M را با "( Δ*: Q × Σ* → "P"(Q" تعریف کرد بدین صورت که:
و ساختار اتومات وجود دارد که چند حالت اولیه را به یک حالت اولیه تبدیل می‌کند. یرای آگاهی بیشتر از تعریف رسمی می‌توانید صفحه نظریه اتوماتا را ببینید.
در این مثال یک ماشین ان‌اف‌ای با الفبای دوتایی شرح داده شده‌است. این ماشین تشخیص می‌دهد که آیا یک رشته ورودی تعدادی زوج صفر در بر دارد یا تعدادی زوج یک.
اتوماتون M را به صورت در نظر می‌گیریم: "M" = ("Q", Σ, "T", "s", "F")
ماشین‌های تعین‌پذیر حالات متناهی DFA : به آن‌دسته از ماشین‌های حالات متناهی اطلاق می‌شود که در آن‌ها به ازاء هر دوتائی شامل حالت و ورودی یک و فقط یک امکان برای عبور به حالت بعدی وجود داشته باشد.
ماشین تعیین ناپذیر با ε حرکت:این اتومات‌ها می‌توانند رابطه انتقال را تغییر دهند و به این شکل دربیاورند:("Δ : "Q" × (Σ ∪{ε}) → "P"("Q
به ازای هر DFA , NFA وجود دارد که دارای زبان صوری یکسان‌اند.DFA را می‌توان به کمک ساختمان پاورست ساخت. و همچنین مهم است که بتوان ساختارهای NFAها را به ساختار DFAهایی با کیفیت تر تبدیل کرد. البته ممکن است که اگر یک NFA دارای n وضیعت باشد آنگاه ساختار DFA دارای ۲ وضیعت باشد که این عدد نمادی در بعضی موارد در مقادیر بزرگ می‌تواند مشکل ساز باشد. ماشین با یک وضیعت اولیه کار خودش شروع می‌کند و رشته‌ای از نمادها را دریافت می‌کند. اتوماتا حالت اولیه را توسط ماشین‌های حالات متناهی " Δ" به حالت جدید تبدیل می‌کنند. توجه کنیم که وضیعت NFA تنها به حالت حاضر بستگی ندارد بلکه به ورودی‌های بعدی نیز ریط دارد. تا زمانی که تمام ورودی‌های بعدی اتفاق نیفتند غیرممکن است که وضیعت ماشین را متوجه شویم. زمانی که NFA دریافت ورودی را تمام کرد آنگاه درمرحله پذیرش است و اعلام می‌کند رشته پذیرفته شدهاست در غیر این صورت رشته را رد می‌کند.
به رشته‌هایی که NFA آن را میپذیرند یک زبان مورد پذیرش NFA گویند. این زبان ,زبان منظم است.
راه‌های بسیاری برای اجرا NFA وجود دارد که برخی از آن‌ها عبارتند از :
۱- آن را به DFA معادل تبدیل می‌کنیم. در برخی موارد این کار سبب افزایش تصاعدی حجم ماشین و بنابراین به وجود آمدن فضاهای کمکی متناسب با تعداد حالت‌های NFA می‌شود(برای نگهداری مقدار حالت برای هر حالت در NFA حداکٹر به یک بیت حافظه نیاز است)
۲-یک ساختمان داده برای تمام حالاتی که ماشین ممکن است در حال حاضر در آن باشد نگهداری کنیم. در مصرف آخرین ورودی که ماشین می‌گیرد، اگر یکی از این حالت‌ها حالت نهایی باشد آن رشته را ماشین می پذیرد. اگر برای هر حالت NFA یک بیت هزینه شود همانند روش قبلی در بدترین حالت زمان گرفته می‌شود.
DFA و NFA از این نظر به هم شباهت دارند که اگر NFA توسط زبانی شناخته شوند , DFA نیز توسط آن زبان شناخته می‌شود. که توجه به این خاصیت مهم و مفید است. مفید است زیرا ساختن یک NFA از یک زبان راحت‌تر از ساختن DFA از آن زبان است. و از این نظر اهمیت دارد که NFA می‌تواند پیچیدگی بسیار از مسائل را که درنظریه محاسبات را کاهش دهد. به‌طور مثال اثبات closure properties از زبان منظم به وسیله NFA ساده‌تر از DFA است.