تصغير الأوتومات
نقصد بتصغير الأوتومات (minimization) إيجاد أوتومات مكافئ يحتوي على أقل عدد ممكن من الحالات. فحتى الأوتومات الذي لا يحتوي على أي حالة زائدة يمكن تبسيطه أكثر.
مثال تمهيدي
لنأخذ الأوتومات الآتي:
لا يقبل هذا الأوتومات إلا الكلمتين 01 و 11. ومن الواضح أنه يوجد أوتومات أبسط بثلاث حالات يقبل اللغة نفسها. فيمكن دمج الحالتين q1 و q2 في حالة جديدة واحدة {q1, q2}، فتتجه الانتقالات التي كانت تؤدي إلى الحالة q1 أو q2 إلى الحالة الجديدة، وكذلك الانتقالات الخارجة من q1 و q2. فنحصل على الأوتومات الآتي:
من الواضح أنّ هذا الأوتومات يقبل اللغة نفسها التي يقبلها الأوتومات السابق، وعدد حالاته أقل.
تكافؤ الحالات
ليكن لدينا الأوتومات A = ⟨Q, Σ, δ, q0, F⟩. نعرّف لغة الحالة q ∈ Q، ونرمز لها بالرمز L(q)، بأنها
أي نغيّر الحالة الابتدائية للأوتومات A من q0 إلى q، ونحسب اللغة التي يقبلها هذا الأوتومات. بعبارة أخرى: في اللغة L(q) كل الكلمات w التي تحقق أننا ننتقل في الأوتومات A بالكلمة w من الحالة q إلى حالة نهائية من حالاته. فإذا عدنا إلى الأوتومات السابق، كان L(q1) = {1}.
نقول إنّ الحالتين المختلفتين q1 و q2 متكافئتان إذا كان
ما معنى ذلك؟ إذا كانت الحالتان q1, q2 متكافئتين، وجعلنا كلاً منهما الحالة الابتدائية للأوتومات، فإنهما تولّدان اللغة نفسها. بعبارة أخرى: إذا وصل الأوتومات إلى التشكيل ⟨q1, w⟩ والتشكيل ⟨q2, w⟩، فيجب أن يقبل في الحالتين أو أن يرفض في الحالتين.
ولنعد إلى الأوتومات السابق: الحالتان q1 و q2 متكافئتان، لأننا إذا كنا في الحالة q1، فلا يمكننا أن نقبل كلمة المدخلات إلا إذا كان الجزء غير المقروء منها مساوياً 1. والأمر نفسه إذا كنا في الحالة q2.
فالمقصود بتصغير الأوتومات إذن أن نجد الحالات المتكافئة ونحذفها بدمجها في حالة جديدة واحدة، كما فعلنا في المثال السابق.
طريقة إيجاد الحالات المتكافئة
ما الحالات التي لا تكون متكافئة بالتأكيد؟ إذا أخذنا حالة نهائية وحالة غير نهائية، فلن تكونا متكافئتين بالتأكيد، لأنّ لغة الحالة النهائية تختلف عن لغة الحالة غير النهائية: فالحالة النهائية تقبل الكلمة ε بالتأكيد، والحالة غير النهائية لا تقبلها. نعرض الطريقة مباشرة على مثال. ليكن لدينا الأوتومات الآتي:
نبدأ بإنشاء مجموعتين من الحالات
ننشئ الآن جدول الانتقالات ونحتفظ بالمعلومة عن المجموعتين S1 و S2:
نعدّل الآن الجدول، فبدلاً من أن نكتب فيه الحالات التي ننتقل إليها بالرمز المعطى، نكتب فقط المجموعة التي ننتقل إليها. فمثلاً من الحالة q3 ننتقل بالرمز 0 إلى الحالة q5 التي تقع في المجموعة S2. فنكتب في الجدول S2 بدلاً من q5:
نقسم الآن المجموعتين كلتيهما تقسيماً أدق. فنضع في المجموعة نفسها دائماً الحالات التي تنتقل إلى المجموعات نفسها لكل الرموز. فمثلاً لن تكون الحالتان q3 و q6 في مجموعة واحدة، لأنهما لا تنتقلان إلى المجموعة نفسها لا بالرمز 0 ولا بالرمز 1. وعلى العكس، تكون الحالتان q1 و q2 في مجموعة واحدة، لأنه ليس لأيّ منهما انتقال للرمز 0، وكلتاهما تنتقل بالرمز 1 إلى المجموعة S1. فننشئ المجموعات الجديدة:
الانتقالات متماثلة في كل مجموعة. نسمّي المجموعات الجديدة، ونبحث مرة أخرى عن المجموعة الجديدة التي تتجه إليها كل حالة:
نقسم المجموعات الآن مرة أخرى. لكننا نرى أنه لا يمكن إجراء أي تقسيم آخر، فسنحصل على المجموعات نفسها: للحالتين q1 و q2 الانتقالات نفسها بين المجموعات، لكنهما في مجموعة واحدة من قبل، ولا توجد في المجموعة S4 أي حالة أخرى. انتهت خوارزمية إيجاد الحالات المتكافئة. ويكفي أن نختار من كل مجموعة حالة واحدة ونحذف الباقي، فتتجه كل الانتقالات التي كانت تؤدي إلى الحالات المحذوفة إلى الحالة الواحدة التي اخترناها.
فيمكننا أن نختار أن تكون حالات أوتوماتنا الجديد q3, q6, q0, q1, q4، ونحذف الحالتين q2 و q5. فتتجه الآن كل الانتقالات التي كانت تؤدي إلى q2 إلى q1، وكل الانتقالات التي كانت تؤدي إلى q5 إلى q4:
خطوات تصغير الأوتومات
- نحذف الحالات التي لا يمكن الوصول إليها،
- نحذف الحالات الزائدة،
- نحذف الحالات المتكافئة.
المصادر
المحتويات: الحالات التي لا يمكن الوصول إليها, الحالات الزائدة, تصغير الأوتومات