ماشین محدود غیرمبهم

در نظریه ماشین ها ، ماشین محدود نامتناهی (UFA) یک نوع به خصوص از ماشین غیرقطعی محدود(NFA) میباشد. هر ماشین محدود قطعی ( DFA ) یک UFA هست اما برعکسش صادق نیست. DFA و UFA و NFA دقیقاً همان کلاس زبان رسمی را میشناسد. از یک طرف یک NFA میتواند به طور نمادین کوچکتر از یک DFA معادل باشد. از یک طرف بعضی از مشکلات میتواند روی DFA ها به راحتی حل شود و روی UFA ها نه.
برای مثال یک ماشین داده شده A را در نظر بگیرید ، یک ماشین A که میتواند مکمل A را بپذیرد میتواند در زمان خطی محاسبه شود که A یک DFA هست ، معلوم نیست که آیا میتوان آن را در زمان چندجمله ای برای UFA انجام داد. از این رو UFA ها ترکیبی از دنیاهای DFA و NFA هاست . در بعضی موارد آنها منجر به ماشین کوچکتر از DFA و الگوریتم های سریع تر از NFA میشوند.
یک NFA به طور رسمی با ۵-تاپل نشان داده میشود ، ( A=(Q, Σ, Δ, q0, F . برای هر کلمه w = a1a2 … an یک UFA چنین است که یک NFA میباشد . در بیشتر موارد یک دنباله ای از حالات r0,r1, …, rn در Q با شرایط زیر وجود دارد :
1. r0 = q0