✖

الحالات الزائدة

قد تكون في الأوتومات المنتهي حالات لا يمكن الوصول منها إلى حالة نهائية، فلا فائدة منها. نسمّي هذه الحالات الحالات الزائدة (redundant states). ونريد عادةً أن نحذفها، لأنها لا تفعل شيئاً سوى تعقيد الأوتومات كله دون فائدة.

مثال على الحالات الزائدة

ليكن لدينا الأوتومات المنتهي الآتي:

نرى أننا إذا وصلنا إلى الحالة q4 أو q5، فلن نتمكن أبداً من الوصول إلى إحدى الحالتين النهائيتين q1 أو q2. فهاتان الحالتان زائدتان، ويمكننا أن نحذفهما ببساطة، فنحصل على أوتومات جديد مكافئ للأوتومات الأصلي، أي يقبل اللغة نفسها. وبعد حذف الحالات الزائدة يصبح الأوتومات كما في الشكل الآتي:

وهو يقبل اللغة نفسها. ومع ذلك توجد مواقف يكون من المناسب فيها وجود بعض الحالات الزائدة، كما عند إنشاء الأوتومات الكامل.

تعريف الحالة الزائدة

ليكن لدينا الأوتومات المنتهي A = ⟨Q, Σ, δ, q0, F⟩. نقول إنّ الحالة q ∈ Q زائدة إذا لم توجد أي كلمة w ∈ Σ∗ وأي حالة qf ∈ F بحيث

⟨q,w⟩↦∗⟨qf,ε⟩.

طريقة حذف الحالات الزائدة

نفرض أنّ في المدخلات الأوتومات A = ⟨Q, Σ, δ, q0, F⟩، وهو خالٍ من الحالات التي لا يمكن الوصول إليها. سنجد تدريجياً الحالات التي تؤدي إلى الحالات النهائية، ثم الحالات التي تؤدي إلى الحالات التي تؤدي إلى الحالات النهائية، وهكذا مرة بعد مرة. وبذلك نحصل على مجموعة كل الحالات غير الزائدة. نضع في البداية S0 = F. ثم ننشئ المجموعات التالية Si لكل i ∈ ℕ وفق القاعدة الآتية:

Si={q∈Q|∃a∈Σ:δ(q,a)∈Si−1}∪Si−1

ويمكننا أن نعبّر عن المجموعة الناتجة من كل الحالات غير الزائدة كما يلي:

⋃i=1∞Si.

وعن مجموعة الحالات الزائدة بالعلاقة

Q∖⋃i=1∞Si.

بعبارة أخرى: إذا كان Si = Si + 1، فإنّ المجموعة Q ∖ Si تحتوي على الحالات الزائدة. نوضّح الطريقة على الأوتومات الآتي:

نضع أولاً المساواة S0 = {q1, q2}. ثم ننشئ المجموعة S1 بأن نضيف إلى المجموعة S0 كل الحالات التي تؤدي إلى إحدى حالات المجموعة S0. فنضيف الحالتين q0 و q3، لأنّ من q0 يخرج انتقال إلى q1، ومن q3 يخرج انتقال إلى q2. فنحصل على S1 = {q0, q1, q2, q3}. وبما أنّ S0 ≠ S1، نتابع.

ننشئ المجموعة S2. فنبحث عن كل الحالات التي يمكن الوصول منها إلى S1 وليست بعد في S1. وهي حالة واحدة، q6، يمكن الوصول منها إلى الحالة q3. فنحصل على S2 = {q0, q1, q2, q3, q6}. وبما أنّ S1 ≠ S2، نتابع.

ننشئ المجموعة S3. هل توجد حالة جديدة يمكن الوصول منها إلى إحدى حالات S2؟ لا توجد، فمن الحالتين q4 و q5 لا يمكن الوصول إلى أي حالة من حالات S2، وباقي الحالات موجودة في S2 من قبل. إذن S3 = {q0, q1, q2, q3, q6}. وبما أنّ S2 = S3، تنتهي الخوارزمية، وتمثّل المجموعة S2 مجموعة الحالات غير الزائدة. أما المجموعة {q4, q5} فهي مجموعة الحالات الزائدة.

ننشئ صورياً الأوتومات المكافئ الجديد الخالي من الحالات الزائدة كما يلي. لدينا الأوتومات A = ⟨Q, Σ, δ, q0, F⟩، وننشئ له أوتوماتاً مكافئاً A′ = ⟨Q′, Σ, δ′, q0, F⟩ خالياً من الحالات الزائدة.

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) إذا كان δ(q, a) ∈ Q′، وإلا فإنّ δ′(q, a) غير معرَّفة

المصادر

المحتويات: الحالات التي لا يمكن الوصول إليها, الحالات الزائدة, تصغير الأوتومات