محاكاة الأوتومات غير الحتمي
إذا كان لدينا أوتومات غير حتمي وأردنا أن نعرف هل يقبل كلمة معيّنة، فيمكننا أن نحوّله إلى أوتومات حتمي، أو أن نجرّب ذلك بطريقة ما، أو أن نستعمل خوارزمية تحاكي عمل الأوتومات غير الحتمي (NFA).
مبدأ الخوارزمية
نوضّح المبدأ على مثال مناسب. ليكن لدينا الأوتومات الآتي:
هذا أوتومات منتهٍ غير حتمي يقبل لغة ما، ولا يهمنا الآن أي لغة هي. سنعرض كيف يمكن أن يسير حساب هذا الأوتومات لكلمة المدخلات 11001. والفكرة أن نعالج رمزاً من الكلمة وننظر إلى كل الحالات التي يمكننا الوصول إليها بفضل الانتقالات المتعددة للرمز نفسه. نحفظ كل هذه الحالات، وفي الخطوة التالية نفرض أننا «في كل هذه الحالات في آن واحد»، ونبحث عن الحالات التي يمكننا الوصول إليها منها.
نحفظ إذن مجموعة الحالات التي يمكن أن نكون فيها، والجزء الذي لم يُقرأ من الكلمة. فيكون لدينا في البداية الثنائي ⟨{q0}, 11001⟩. نبدأ من الحالة q0 (الحالة الابتدائية) وفي المدخلات الكلمة 11001. والأوتومات كما في الشكل الآتي، والحالة التي نحن فيها مميَّزة باللون الأحمر والخط العريض:
الرمز الأول هو 1، ومن الحالة q0 يخرج انتقال واحد فقط للرمز 1، فنصل إلى الحالة q1. نحفظ الثنائي ⟨{q1}, 1001⟩. ويصبح الأوتومات كما يلي:
نتابع. الجزء غير المقروء من الكلمة هو 1001، فنبحث مرة أخرى عن الانتقالات للرمز 1. وهي الآن انتقالان: عودة إلى الحالة q0، وانتقال إلى الحالة q3. وننطلق الآن إلى الحالتين معاً. فنحفظ الثنائي ⟨{q0, q3}, 001⟩.
ما المنطق في ذلك؟ نعرف أنه يوجد طريق من الحالة الابتدائية بالكلمة 11 إلى الحالة q3، وطريق آخر إلى الحالة q0. ولا نعرف بعد أي الفرعين سيفيدنا، فنحفظ الاثنين ببساطة. نتابع. في المدخلات الرمز 0. وعلينا الآن أن ننظر إلى الانتقالات من q0 وإلى الانتقالات من q3 أيضاً. فمن الحالة q0 تخرج انتقالات إلى الحالتين q1 و q2، ومن الحالة q3 يعود انتقال إلى q1. نأخذ كل هذه الحالات، فنحصل على الثنائي ⟨{q1, q2}, 01⟩:
لكننا لم ننتهِ بعد من هذه الخطوة. نرى أنّ من الحالة q2 يخرج انتقال إبسيلون إلى الحالة q4. ونعرف أنّ انتقال إبسيلون يمكن «سلوكه في أي وقت» دون قراءة رمز آخر. أي يمكننا، دون أن نقرأ رمزاً آخر من كلمة المدخلات، أن ننتقل أيضاً إلى الحالة q4. فنضيف الحالة q4 إلى الحالات التي يمكن أن نكون فيها: ⟨{q1, q2, q4}, 01⟩. ونلوّن الأوتومات كما يلي:
في المدخلات بعد ذلك 0. ننظر إلى الحالات التي يمكننا الانتقال إليها من الحالات الثلاث التي نحن فيها. من q1 لا يمكننا الانتقال إلى أي حالة، لأنه لا يوجد انتقال للرمز 0، فينتهي الحساب في هذا الفرع. ومن الحالة q4 لا نصل أيضاً إلى أي حالة. أما من الحالة q2 فنعود إلى الحالة q2. ولأنّ من الحالة q2 يخرج مرة أخرى انتقال إبسيلون إلى الحالة q4، فيمكننا أن نصل إلى الحالة q4 أيضاً. إذن نصل من مجموعة الحالات {q1, q2, q4} بالرمز 0 إلى مجموعة الحالات {q2, q4}، ونحصل على الثنائي ⟨{q2, q4}, 1⟩:
وأخيراً في المدخلات الرمز 1. من الحالة q2 لا نصل إلى أي حالة، فينتهي الحساب في هذا الفرع. أما من الحالة q4 فنصل إلى الحالتين q3 و q5. ونحصل على الثنائي ⟨{q3, q5}, ε⟩:
قرأ الأوتومات الآن الكلمة كلها، و»يوجد» في حالتين: q3, q5. وبما أنّ إحداهما على الأقل حالة نهائية، فإنّ الأوتومات يقبل الكلمة 11001.
الخوارزمية
نحتاج أولاً إلى دالة تأخذ وسيطاً هو مجموعة من الحالات، وتحسب الحالات التي يمكننا أن نصل إليها أيضاً بانتقالات إبسيلون. فمدخلاتها الأوتومات ⟨Q, Σ, δ, q0, F⟩ ومجموعة الحالات States، ومخرجاتها مجموعة شاملة لهذه الحالات تضم الحالات التي يمكن الوصول إليها بانتقالات إبسيلون. نسمّي هذه العملية انغلاق إبسيلون (epsilon closure) للمجموعة States.
نستعمل هذه الدالة في دالة تحاكي عمل الأوتومات غير الحتمي. ومدخلاتها الأوتومات وكلمة المدخلات w = w1w2… wn ومجموعة الحالات التي يوجد فيها الأوتومات حالياً. ومخرجاتها الإجابة «نعم» أو «لا»، بحسب ما إذا كان الأوتومات يقبل الكلمة المعطاة أو لا يقبلها.
إذا أردنا أن نتحقق هل يقبل الأوتومات الكلمة w، نستدعي الدالة كما يلي: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0})).
المصادر
المحتويات: الأوتومات المنتهي, الأوتومات الكامل, الأوتومات المنتهي غير الحتمي, محاكاة الأوتومات غير الحتمي, تحويل NFA إلى DFA