مرجع
آخر الزيارات

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

1٬235 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (NFA) في المعلوماتية النظرية هو ماكينة محدودة الحالات حيث قد يؤدي كل زوج مكون من رمز من رموز المدخلات وأحد الحالات إلى عدد من الحالات في الخطوة التالية، وهذا ما…. في هذه المقالة 12 قسماً: «وبالمثل إذا كانت و فإن»، «خصائص NFA-ε» و«الخصائص» وغيرها.
المحتويات
  1. وبالمثل إذا كانت و فإن
  2. خصائص NFA-ε
  3. الخصائص
  4. التعريف الشكلي
  5. مقدمة بسيطة
  6. مجموعة محدودة من رموز المدخلات Σ
  7. التنفيذ
  8. مسلسل لغتين نمطيتين هي لغة نمطية
  9. F = {s1, s3}, and
  10. مثال
  11. حالة ابتدائية (أو بداية) q0 ∈ Q
  12. تطبيقات NFA-ε

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

من جهة ثانية، قدم مايكل و. رابين ودانا سكوت نموذج التشغيل المحدود غير القطعي عام 1959، وهما من بينا كذلك مكافأته لنموذج التشغيل المحدود القطعي.

وبالمثل إذا كانت و فإن

  • p0 E({q0})
  • pi E(T(pi-1, xi )) for i = 1,..., n
  • pn F.

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

خصائص NFA-ε

  • .
  • لأي مجموعة جزئية، تعرف ε-closure من P كـ
  • .
  • نقلات إبسلون انتقالية فيمكن إثبات أن لكل و، إذا كان و، فإن .

كذلك، لكل نكتب فقط إذا كان يمكن الوصول من إلى عن طريق صفر أو أكثر من أسهم ، بمعنى أن فقط إذا كان هناك بحيث

.

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

الخصائص

في هذا الإطار، وتسمى مجموعة المتسلسلات التي قبلها الـNFA اللغة التي يقبلها، وهي لغة نمطية.

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

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

التعريف الشكلي

مجموعة محدودة من الحالات Q

ومن ناحية أخرى، هناك تعريفان لنوعين مماثلين من NFA: NFA وNFA-epsilon. يعرف النموذج العادي بالمرتب الخماسي (Q, Σ, T, q0, F) الذي يتألف من

مقدمة بسيطة

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

من جانب آخر، يستهلك أي NFA - وكذلك أي 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 : Q × Σ → P(Q)

التنفيذ

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

إضافةً إلى ذلك، عمل نسخ متعددة. لكل قرار يؤدي إلى n اتجاه يقوم الـNFA بعمل n-1 نسخة من الماكينة، كل منهم تدخل حالة منفردة، وبعد استخدام آخر رمز إذا كانت نسخة واحدة على الأقل تقف في حالة قبول فالـNFA يقبل المتسلسلة (وهذا كذلك يتطلب مساحة تتناسب خطيا مع عدد حالات الـNFA ، حيث يمكن أن يوجد ماكينة لكل حالة)

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

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

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

مسلسل لغتين نمطيتين هي لغة نمطية

نجمة كليين لأي لغة نمطية هي لغة نمطية

F = {s1, s3}, and

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

مثال

  • M = (Q, Σ, T, s0, F) حيث
  • Σ = {0, 1},
  • Q = {s0, s1, s2, s3, s4},
  • E({s0}) = { s0, s1, s3 }

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

حالة ابتدائية (أو بداية) q0 ∈ Q

T : Q × (Σ ∪{ε}) → P(Q).

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

في هذا الإطار، مجموعة من الحالات F تتميز بأنها حالات قبول (أو نهائية) F ⊆ Q

وفي هذا الصدد، P(Q) هنا تشير إلى المجموعة المضاعفة من Q، وفي NFA الذي يحتوي على حركات إبسلون (أو NFA-lambda أو NFA-epsilon) تستبدل دالة الانتقال بأخرى تقبل المتسلسلة الفارغة ε كأحد مدخلاتها، بالتالي

تطبيقات NFA-ε

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

اتحاد لغتين نمطيتين هو لغة نمطية

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.