آلة محدودة الحالات غير قطعية

الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (NFA) في المعلوماتية النظرية هو ماكينة محدودة الحالات حيث قد يؤدي كل زوج مكون من رمز من رموز المدخلات وأحد الحالات إلى عدد من الحالات في الخطوة التالية، وهذا ما يميز هذا النموذج عن نموذج التشغيل الذاتي المحدود القطعي (DFA) حيث تكون الحالة المحتملة التالية حالة واحدة فقط. برغم أن لكل من النموذجين تعريف مختلف، يمكن إثبات أنهما متساويان في النظرية الشكلية حيث يمكن إنشاء DFA مكافئ لأي NFA والعكس صحيح، وهذا ما يسمى بإنشاء المجموعة المضاعفة. يتعرف كلا النموذجين على اللغات النمطية فقط. تدرس نماذج التشغيل المحدودة غير القطعية أحيانا باسم مساحة التنقل محدودة النوع. يعتبر نموذج التشغيل الاحتمالي الذي يعطي لكل نقلة من حالة إلى أخرى احتمالية نموذجا أعم من نموذج التشغيل المحدود غير القطعي.
قدم مايكل و. رابين ودانا سكوت  نموذج التشغيل المحدود غير القطعي عام 1959، وهما من بينا أيضا مكافأته لنموذج التشغيل المحدود القطعي.

مقدمة بسيطة

يستهلك أي NFA - وكذلك أي DFA - متسلسلة من رموز المدخلات، وينتقل إلى حالة جديدة بعد كل رمز حتى ينتهي من جميع الرموز. 
وهو يخالف الـDFA في كونه غير قطعي، بمعنى أن أي رمز من رموز المدخلات قد يؤدي إلى واحدة من عدد من الحالات المحتملة، بالتالي الحالة التالية في التعريف الشكلي هي عنصر من عناصر المجموعة المضاعفة للحالات، هذا العنصر - هو نفسه عبارة عن مجموعة - يمثل مجموعة جزئية من جميع الحالات يتم التعامل معها جميعا في نفس الوقت.
NFA-lambda هو امتداد للـ NFA (يعرف أيضا باسم NFA-epsilon أو نموذج NFA بنقلات إبسلون) وهو يتيح الانتقال إلى حالة جديدة بدون استخدام أي من رموز المدخلات، مثلا إذا كان النظام في الحالة 1 والرمز التالي هو a فيمكنه التحرك إلى الحالة 2 بدون استخدام أي رمز، بالتالي هناك التباس: هل النظام في الحالة 1 أم 2 قبل استخدام الحرف a؟ بسبب هذا الالتباس فالكلام عن مجموعة الحالات التي يمكن أن يكون النظام موجود بها أكثر ملاءمة لهذا الوضع، وهكذا قد يكون NFA-epsilon في أحد حالات المجموعة {1, 2} قبل استخدامه للحرف a، وهذا معناه أننا يمكننا تخيل وجود الـNFA في الحالة 1 و2 في نفس الوقت، وهذا يعطينا إشارة من عملية إنشاء المجموعة المضاعفة: يعرف الـDFA المكافئ للـ NFA بأنه النموذج الموجود عند الحالة q={1,2}. التحرك إلى حالات جديدة بدون استخدام أي من رموز المدخلات يسمى نقلات لامدا أو نقلات إبسلون، وتأخذ عادة الرموز اليونانية λ وε.
مفهوم قبول متسلسلة في NFA يماثل نفس المفهوم في DFA، بعد استخدام آخر رمز في المدخلات الـNFA يقبل المتسلسلة فقط إذا كانت هناك مجموعة من النقلات التي تنتهي به إلى حالة قبول، كذلك يرفض المتسلسلة إذا لم ينته إلى حالة قبول مهما كانت النقلات المستخدمة.

الخصائص

تبدأ الماكينة في حالة ابتدائية محددة وتبدأ في قراءة متسلسلة من رموز أبجديتها، يستخدم نموذج التشغيل الذاتي دالة الانتقال T لمعرفة الحالة التالية التي تؤدي إليها الحالة الحالية والرمز الذي تمت قراءته أو المتسلسلة الفارغة، ولكن الحالة التالية في NFA لا تعتمد على عملية الإدخال الحالية فحسب ولكن على عدد عشوائي من عمليات الإدخال اللاحقة أيضا، وحتى حدوث هذه العمليات لا يمكن معرفة الحالة الموجودة عندها الماكينة. إذا كانت الماكينة في حالة قبول بعد قراءتها لكل رموز المدخلات يقال أن الـNFA يقبل هذه المتسلسلة، غير هذا يقال أنه يرفضها.
وتسمى مجموعة المتسلسلات التي قبلها الـNFA اللغة التي يقبلها، وهي لغة نمطية.
لكل NFA يوجد ماكينة قطعية محدودة الحالات (DFA) تقبل نفس اللغة، بالتالي يمكن تحويل أي NFA إلى DFA بغرض عمل ماكينة (ربما تكون) أبسط، ويمكن عمل هذا باستخدام عملية إنشاء المجموعة المضاعفة التي قد تؤدي إلى زيادة أسية في عدد الحالات المطلوبة، يوجد هنا الإثبات الشكلى لعملية إنشاء المجموعة المضاعفة.