تحويل NFA إلى DFA
سنعرض كيف نحوّل الأوتومات غير الحتمي إلى أوتومات حتمي، وبذلك نثبت أنّ القدرة الحسابية للأوتومات غير الحتمية والأوتومات الحتمية متكافئة.
الفكرة الأساسية
ليكن لدينا الأوتومات غير الحتمي ⟨QN, ΣN, δN, q0, FN⟩ دون انتقالات إبسيلون. ننشئ الأوتومات الحتمي ⟨QD, ΣD, δD, p0, FD⟩ بحيث
- QD ⊆ 2QN
- ΣD = ΣN
- p0 = {q0}
- FD = {Q ∈ QD | Q ∩ FN ≠ ∅}
ونعرّف دالة الانتقال δD كما يلي:
ما معنى ذلك؟ يمكن أن يكون الأوتومات غير الحتمي في عدة حالات في آن واحد، فقد نصل مثلاً إلى موقف يكون فيه أوتوماتنا غير الحتمي في الحالات {q0, q1}. وبقراءة الرمز التالي، وليكن 1، قد نصل إلى مجموعة الحالات {q0, q2, q3}. وفي النسخة الحتمية من الأوتومات نفسه يظهر ذلك بأن ننشئ حالتين نسمّيهما {q0, q1} و {q0, q2, q3}، ونرسم بينهما انتقالاً للرمز 1. فننتقل صورياً من حالة واحدة إلى حالة أخرى، لكننا نعرف بفضل التسمية أننا كنا سنكون في الأوتومات غير الحتمي في حالتين ثم في ثلاث حالات.
مثال على التحويل
ليكن لدينا الأوتومات غير الحتمي الآتي:
لكي ننشئ الأوتومات الحتمي، نحتاج قبل كل شيء إلى إنشاء دالة انتقال جديدة. ويساعدنا في ذلك جدول نكتب فيه كل الانتقالات. ويكون الجدول في البداية كما يلي:
سيكون في العمود الأيسر عند انتهاء الخوارزمية كل حالات الأوتومات الحتمي، والجدول المكتمل يحدد لنا دالة الانتقال. نكتب الآن في الجدول الحالات التي نصل إليها إذا كنا في الحالات {q0} وفي المدخلات الرمزان 0 و 1.
من الحالة q0 يخرج للرمز 0 انتقال إلى الحالة q1 وحدها، أما للرمز 1 فيخرج انتقال إلى الحالتين q1 و q2. نضيف الآن إلى الجدول حالتين جديدتين: {q1} و {q1, q2}. لماذا؟ كلما كتبنا في الجدول مجموعة حالات ليست بعد في العمود الأيسر، أضفناها إليه.
ثم نملأ الجدول مرة أخرى. وعند الحالة {q1, q2} يجب ألّا ننسى فحص الحالتين كلتيهما، أي نأخذ اتحاد الحالات التي نصل إليها من الحالة q1 والحالات التي نصل إليها من الحالة q2.
حصلنا على بعض الحالات الجديدة التي يجب أن نضيفها إلى الجدول:
…ونكمل الانتقالات مرة أخرى:
الحالات {q0, q1, q3} و {q1} و {q1,q2} موجودة لدينا من قبل، فنضيف الحالة {q0,q1,q2,q3} وحدها.
لم نضف أي حالة جديدة، إذن اكتمل الجدول. ولم يبقَ إلا أن نرسم المخطط. حالات الأوتومات الحتمي في العمود الأول، والانتقالات للرمزين 0 و 1 في العمودين الآخرين. وكل حالة تحتوي على حالة نهائية من الأوتومات الأصلي تكون حالة نهائية في هذا الأوتومات أيضاً، أي أنّ كل حالة تحتوي على q3 حالة نهائية. ويكون الأوتومات كما في الشكل الآتي:
ويمكننا أن نتحقق من أنّ الأوتومات يعمل فعلاً بصورة صحيحة. لنجرّب قبول الكلمة 11001. في الأوتومات الحتمي نسلك الطريق
ويقبل الأوتومات الكلمة، لأنّ الحالة الأخيرة {q0, q1, q2, q3} نهائية. وفي الأوتومات غير الحتمي نصل أثناء المحاكاة إلى الحالات نفسها، أي نبدأ من الحالة q0 ونصل بالرمز 1 إلى الحالتين {q1, q2}. ثم يوصلنا الرمز 1 التالي إلى الحالتين {q0,q3}، وهكذا بالنسبة إلى الرموز التالية. وفي النهاية نجد أنفسنا في كل الحالات {q0, q1, q2, q3}، فيقبل الأوتومات الكلمة.
المصادر
المحتويات: الأوتومات المنتهي, الأوتومات الكامل, الأوتومات المنتهي غير الحتمي, محاكاة الأوتومات غير الحتمي, تحويل NFA إلى DFA