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

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

مثال

در این مثال یک ماشین ان‌اف‌ای با الفبای دوتایی شرح داده شده است. این ماشین تشخیص می‌دهد که آیا یک رشته ورودی تعدادی زوج صفر در بر دارد یا تعدادی زوج یک.

اتوماتون M را به صورت در نظر می‌گیریم:

M = (Q, Σ, T, s₀, F)

• Σ = {0, 1},
• Q = {s₀, s₁, s₂, s₃, s₄},
• E({s₀}) = { s₀, s₁, s₃ }
• F = {s₁, s₃}, and
• The transition function T can be defined by this state transition table:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

منابع

• Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5 [۱]