در تئوری محاسبات، اتوماتون تعیین ناپذیر متناهی یا اتوماتون غیرقابل تعیین متناهی یا ان اف اِی ( Nondeterministic finite automaton - NFA ) به اتوماتون هایی گفته می شود که در مورد آن ها برای برخی از دوتایی های حالت و سمبل ورودی امکان عبور به بیشتر از یک حالت جدید اجازه داده شده باشد. NFA در بعضی موارد با نام Subshift of finite type شناخته می شود. NFA به راه های متعددی، تعمیم داده شده است: اتومات تعیین ناپذیر با ε حرکت[ ۱] ، اتوماتون پشته ای، اتومات ω ای[ ۲] ، اتومات احتمالی[ ۳] .
یک NFA , مانند DFA به رشته ای از نمادها برای ورود نیازمند است. برای هر نماد ورودی، NFA به حالتی جدیدی میرود تا بتواند تمام ورودی جدید را استفاده کند. برخلاف NFA , DFA غیر قطعی است و برای هر نماد ورودی , حالتی بعدی می تواند هر کدام از چندین حالت ممکن باشد , بنابراین در تعریف رسمی حالت بعدی عضوی از مجموعه توانی از وضیعت هاست که در یک زمان در نظر گرفته می شود. مفهوم پذیرفتن یک ورودی در NFA به مانند DFA است. DFA زمانی پذیرفته می شود اگر و تنها اگر که آخرین نماد ورودی استفاده شده ِهنوز تعدادی انتقال باشد که به حالت مورد انتظار و مورد قبول برسیم. معادلاَ زمانی به رد می شود که بدون توجه به آنچه انتقال پیدا کرده است , به حالت مورد قبول نرسیم.
یک NFA به طور معمول با ۵ عامل معرفی می کنیم: ( Q, Σ, Δ, q0, F ) که در آن:
• Q مجموعه محدودی از وضیعت هاست.
• Σ مجموعه محدودی از وضیعت های ورودی است.
• ( Δ : Q × Σ → P ( Q رابطه انتقال است.
• q0 ∈ Q حالت اولیه است.
• F ⊆ Q مجموعه از حالت مورد قبول است.
حال توجه کنید که منظور از ( P ( Q مجموعه توانی از Q است. فرض کنید که w = a1a2 . . . an مجموعه ورودی باشد ( Σ ) . اتومات به شرطی دنباله w را میپذیرد که شرایط زیر را داشته باشد:
• r0 = q0
• ri+1 ∈ Δ ( ri, ai+1 ) , for i = 0, . . . , n−1
• rn ∈ F.
به عبارت دیگر , شرط اول می گوید که ماشین با q0 شروع به کار می کند. شرط دوم می گوید که ماشین هر کاراکتر رشته w را از حالت خود به حالت تابع Δ انتقال می دهد. و شرط سوم می گوید که ماشین زمانی w میپذیرد که آخرین ورودی w در یکی از حالات مورد قبول ماشین باعث توقف شود. در غیر اینصورت اتومات رشته ورودی را رد می کند. مجموعه ای از رشته هایی که پذیرفته می شوند را با زبان صوری M نشان میدهیم و برای نشان دادن این زبان از ( L ( M استفاده می کنیم.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک NFA , مانند DFA به رشته ای از نمادها برای ورود نیازمند است. برای هر نماد ورودی، NFA به حالتی جدیدی میرود تا بتواند تمام ورودی جدید را استفاده کند. برخلاف NFA , DFA غیر قطعی است و برای هر نماد ورودی , حالتی بعدی می تواند هر کدام از چندین حالت ممکن باشد , بنابراین در تعریف رسمی حالت بعدی عضوی از مجموعه توانی از وضیعت هاست که در یک زمان در نظر گرفته می شود. مفهوم پذیرفتن یک ورودی در NFA به مانند DFA است. DFA زمانی پذیرفته می شود اگر و تنها اگر که آخرین نماد ورودی استفاده شده ِهنوز تعدادی انتقال باشد که به حالت مورد انتظار و مورد قبول برسیم. معادلاَ زمانی به رد می شود که بدون توجه به آنچه انتقال پیدا کرده است , به حالت مورد قبول نرسیم.
یک NFA به طور معمول با ۵ عامل معرفی می کنیم: ( Q, Σ, Δ, q0, F ) که در آن:
• Q مجموعه محدودی از وضیعت هاست.
• Σ مجموعه محدودی از وضیعت های ورودی است.
• ( Δ : Q × Σ → P ( Q رابطه انتقال است.
• q0 ∈ Q حالت اولیه است.
• F ⊆ Q مجموعه از حالت مورد قبول است.
حال توجه کنید که منظور از ( P ( Q مجموعه توانی از Q است. فرض کنید که w = a1a2 . . . an مجموعه ورودی باشد ( Σ ) . اتومات به شرطی دنباله w را میپذیرد که شرایط زیر را داشته باشد:
• r0 = q0
• ri+1 ∈ Δ ( ri, ai+1 ) , for i = 0, . . . , n−1
• rn ∈ F.
به عبارت دیگر , شرط اول می گوید که ماشین با q0 شروع به کار می کند. شرط دوم می گوید که ماشین هر کاراکتر رشته w را از حالت خود به حالت تابع Δ انتقال می دهد. و شرط سوم می گوید که ماشین زمانی w میپذیرد که آخرین ورودی w در یکی از حالات مورد قبول ماشین باعث توقف شود. در غیر اینصورت اتومات رشته ورودی را رد می کند. مجموعه ای از رشته هایی که پذیرفته می شوند را با زبان صوری M نشان میدهیم و برای نشان دادن این زبان از ( L ( M استفاده می کنیم.
