• NFA لتقف على أتمتة محدودة غير حتمية. من السهل إنشاء NFA بدلاً من DFA للغة عادية معينة.
• تسمى الأتمتة المحدودة NFA عندما يكون هناك العديد من المسارات لإدخال محدد من الحالة الحالية إلى الحالة التالية.
• كل NFA ليس DFA، ولكن يمكن ترجمة كل NFA إلى DFA.
• يتم تعريف NFA بنفس طريقة DFA ولكن مع الاستثناءين التاليين، فهو يحتوي على حالات تالية متعددة، ويحتوي على انتقال ε.

في الصورة التالية، يمكننا أن نرى أنه من الحالة q0 للإدخال a، هناك حالتان تاليتان q1 و q2، وبالمثل، من q0 للإدخال b، الحالات التالية هي q0 و q1. وبالتالي، لم يتم تحديد أو تحديد ذلك بإدخال معين إلى أين يجب أن نتجه بعد ذلك. ومن ثم يُسمى هذا FA بالأتمتة المحدودة غير الحتمية.

التعريف الرسمي لـ NFA:

يحتوي NFA أيضًا على خمس حالات مماثلة لـ DFA، ولكن مع وظيفة انتقال مختلفة، كما هو موضح أدناه:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

أين،

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

التمثيل الرسومي للNFA

يمكن تمثيل NFA برسوم بيانية تسمى مخطط الحالة. بحيث:

1. يتم تمثيل الدولة بالقمم.
2. يُظهر القوس المسمى بحرف الإدخال التحولات.
3. يتم تمييز الحالة الأولية بسهم.
4. يتم الإشارة إلى الحالة النهائية بواسطة الدائرة المزدوجة.

مثال 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

حل:

مخطط الانتقال:

الجدول الانتقالي:

في الرسم البياني أعلاه، يمكننا أن نرى أنه عندما تكون الحالة الحالية هي q0، عند الإدخال 0، ستكون الحالة التالية هي q0 أو q1، وعند إدخال واحد ستكون الحالة التالية هي q1. عندما تكون الحالة الحالية هي q1، عند الإدخال 0 ستكون الحالة التالية هي q2 وعند الإدخال 1، ستكون الحالة التالية هي q0. عندما تكون الحالة الحالية هي q2، عند الإدخال 0 تكون الحالة التالية هي q2، وعند الإدخال الأول ستكون الحالة التالية q1 أو q2.

مثال 2:

NFA مع ∑ = {0, 1} يقبل جميع السلاسل ذات 01.

حل:

الجدول الانتقالي:

مثال 3:

NFA بـ ∑ = {0, 1} واقبل كل السلسلة التي يبلغ طولها 2 على الأقل.

حل:

الجدول الانتقالي: