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

الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (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) الذي يتألف من

• مجموعة محدودة من الحالات Q
• مجموعة محدودة من رموز المدخلات Σ
• دالة انتقال T : Q × Σ → P(Q)
• حالة ابتدائية (أو بداية) q0 ∈ Q
• مجموعة من الحالات F تتميز بأنها حالات قبول (أو نهائية) F ⊆ Q

P(Q) هنا تشير إلى المجموعة المضاعفة من Q، وفي NFA الذي يحتوي على حركات إبسلون (أو NFA-lambda أو NFA-epsilon) تستبدل دالة الانتقال بأخرى تقبل المتسلسلة الفارغة ε كأحد مدخلاتها، بالتالي T : Q × (Σ ∪{ε}) → P(Q). يمكن إثبات أن NFA العادي والـ NFA الذي يحتوي على حركات إبسلون متكافئين ، فيمكن إنشاء أحدهما باستخدام الآخر بحيث يقبل كلاهما نفس اللغة.

الخصائص

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

خصائص NFA-ε

لكل $p,q\in Q,$ نكتب $p{\stackrel {\epsilon }{\rightarrow }}q$ فقط إذا كان يمكن الوصول من $p$ إلى $q$ عن طريق صفر أو أكثر من أسهم $\epsilon$، بمعنى أن $p{\stackrel {\epsilon }{\rightarrow }}q$ فقط إذا كان هناك $q_{1},q_{2},\cdots q_{k}\in Q$ بحيث

$q_{1}\in T(p,\epsilon ),q_{2}\in T(q_{1},\epsilon ),\cdots q_{k}\in T(q_{k-1},\epsilon ),q\in T(q_{k},\epsilon )$.

لكل $p\in Q$، تسمى مجموعة الحالات التي يمكن الوصول إليها من p ε-closure أو epsilon-closure من p، وتكتب

$\,E(\{p\})=\{q\in Q:p{\stackrel {\epsilon }{\rightarrow }}q\}$.

لأي مجموعة جزئية$P\subset Q$، تعرف ε-closure من P كـ

$E(P)=\bigcup \limits _{p\in P}E(\{p\})$.

نقلات إبسلون انتقالية فيمكن إثبات أن لكل $q_{0},q_{1},q_{2}\in Q$ و$P\subset Q$، إذا كان $q_{1}\in E(\{q_{0}\})$ و$q_{2}\in E(\{q_{1}\})$، فإن $q_{2}\in E(\{q_{0}\})$.

وبالمثل إذا كانت $q_{1}\in E(P)$ و$q_{2}\in E(\{q_{1}\})$ فإن $q_{2}\in E(P)$

لتكن x متسلسلة من الأبجدية Σ∪{ε}، وليكن M نموذج NFA-ε، يقبل M المتسلسلة x إذا كان يمكن تمثيل x \على هيئة x1x2... xn، بحيث xi ∈ (Σ ∪{ε}) ، ويوجد سلسلة من الحالات p0,p1,..., pn, حيث pi ∈ Q ترضي الشروط الآتية:

1. p₀ $\in$ E({q₀})
2. p_i $\in$ E(T(p_i-1, x_i )) for i = 1,..., n
3. p_n $\in$ F.

التنفيذ

يوجد عدة طرق لتنفيذ نموذج NFA:

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

مثال

المثال التالي يشرح نموذج الـNFA M وأبجديته ثنائية، وهو يحاول معرفة إذا كانت المتسلسلة التي تم إدخالها تحتوي على عدد زوجي من الأصفار أو عدد زوجي من الواحد (لاحظ أن الصفر عدد زوجي أيضا). ليكن M = (Q, Σ, T, s0, F) حيث

• Σ = {0, 1},
• Q = {s0, s1, s2, s3, s4},
• E({s0}) = { s0, s1, s3 }
• F = {s1, s3}, and
• يمكن تعريف دالة الانتقال T بجدول الانتقال بين الحالات التالي:

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

مخطط الحالات لـ M:

يمكن اعتبار M اتحاد لنموذجي DFA: واحد يضم الحالات {S1, S2} والآخر يضم {S3, S4}. يمكن وصف اللغة النمطية التي يقبلها M بهذا التعبير النمطي:

تطبيقات NFA-ε

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

• اتحاد لغتين نمطيتين هو لغة نمطية
• مسلسل لغتين نمطيتين هي لغة نمطية
• نجمة كليين لأي لغة نمطية هي لغة نمطية

$(1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})$