آلة محدودة الحالات غير قطعية
الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (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 يقبل المتسلسلة فقط إذا كانت هناك مجموعة من النقلات التي تنتهي به إلى حالة قبول، كذلك يرفض المتسلسلة إذا لم ينته إلى حالة قبول مهما كانت النقلات المستخدمة.
هناك تعريفان لنوعين مماثلين من NFA: NFA وNFA-epsilon. يعرف النموذج العادي بالمرتب الخماسي (Q, Σ, T, q0, F) الذي يتألف من
P(Q) هنا تشير إلى المجموعة المضاعفة من Q، وفي NFA الذي يحتوي على حركات إبسلون (أو NFA-lambda أو NFA-epsilon) تستبدل دالة الانتقال بأخرى تقبل المتسلسلة الفارغة ε كأحد مدخلاتها، بالتالي
T : Q × (Σ ∪{ε}) → P(Q).
يمكن إثبات أن NFA العادي والـ NFA الذي يحتوي على حركات إبسلون متكافئين ، فيمكن إنشاء أحدهما باستخدام الآخر بحيث يقبل كلاهما نفس اللغة.
تبدأ الماكينة في حالة ابتدائية محددة وتبدأ في قراءة متسلسلة من رموز أبجديتها، يستخدم نموذج التشغيل الذاتي دالة الانتقال T لمعرفة الحالة التالية التي تؤدي إليها الحالة الحالية والرمز الذي تمت قراءته أو المتسلسلة الفارغة، ولكن الحالة التالية في NFA لا تعتمد على عملية الإدخال الحالية فحسب ولكن على عدد عشوائي من عمليات الإدخال اللاحقة أيضا، وحتى حدوث هذه العمليات لا يمكن معرفة الحالة الموجودة عندها الماكينة. إذا كانت الماكينة في حالة قبول بعد قراءتها لكل رموز المدخلات يقال أن الـNFA يقبل هذه المتسلسلة، غير هذا يقال أنه يرفضها.
وتسمى مجموعة المتسلسلات التي قبلها الـNFA اللغة التي يقبلها، وهي لغة نمطية.
لكل NFA يوجد ماكينة قطعية محدودة الحالات (DFA) تقبل نفس اللغة، بالتالي يمكن تحويل أي NFA إلى DFA بغرض عمل ماكينة (ربما تكون) أبسط، ويمكن عمل هذا باستخدام عملية إنشاء المجموعة المضاعفة التي قد تؤدي إلى زيادة أسية في عدد الحالات المطلوبة، يوجد هنا الإثبات الشكلى لعملية إنشاء المجموعة المضاعفة.
لكل formula_1 نكتب formula_2 فقط إذا كان يمكن الوصول من formula_3 إلى formula_4 عن طريق صفر أو أكثر من أسهم formula_5، بمعنى أن formula_2 فقط إذا كان هناك formula_7 بحيث
لكل formula_9، تسمى مجموعة الحالات التي يمكن الوصول إليها من p ε-closure أو epsilon-closure من p، وتكتب
لأي مجموعة جزئيةformula_11، تعرف ε-closure من P كـ
نقلات إبسلون انتقالية فيمكن إثبات أن لكل formula_13 وformula_11، إذا كان formula_15 وformula_16، فإن formula_17.
وبالمثل إذا كانت formula_18 وformula_16 فإن formula_20
لتكن x متسلسلة من الأبجدية Σ∪{ε}، وليكن M نموذج NFA-ε، يقبل M المتسلسلة x إذا كان يمكن تمثيل x \على هيئة x1x2... xn، بحيث xi ∈ (Σ ∪{ε}) ، ويوجد سلسلة من الحالات p0,p1..., pn, حيث pi ∈ Q ترضي الشروط الآتية:
يوجد عدة طرق لتنفيذ نموذج NFA:
المثال التالي يشرح نموذج الـNFA M وأبجديته ثنائية، وهو يحاول معرفة إذا كانت المتسلسلة التي تم إدخالها تحتوي على عدد زوجي من الأصفار أو عدد زوجي من الواحد (لاحظ أن الصفر عدد زوجي أيضا). ليكن
M = (Q, Σ, T, s0, F) حيث 
مخطط الحالات لـ M:
يمكن اعتبار M اتحاد لنموذجي DFA: واحد يضم الحالات {S1, S2} والآخر يضم {S3, S4}.
يمكن وصف اللغة النمطية التي يقبلها M بهذا التعبير النمطي:
يتساوى NFA وDFA حيث أن اللغة التي يتعرف عليها نموذج NFA يتعرف عليها أيضا نموذج DFA والعكس صحيح. إثبات هذا التساوي أمر هام ومفيد، مفيد لأن إنشاء NFA للتعرف على لغة ما يكون أحيانا أسهل من إنشاء DFA للتعرف على نفس اللغة، وهام لأنه يمكن استخدام نماذج الـNFA للتقليل من التعقيد الرياضي المطلوب لإثبات عدد من الخصائص الهامة في نظرية الحوسبة، مثلا إثبات الخصائص الآتية أسهل كثيرا باستخدام الـNFA عن الـ DFA:
formula_24