✖

الحالات التي لا يمكن الوصول إليها

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

مثال على الحالات التي لا يمكن الوصول إليها

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

نرى أننا مهما فعلنا فلن نصل أبداً إلى الحالة q3، لأنه لا يتجه إليها أي انتقال. ولذلك نقول عن الحالة q3 إنها حالة لا يمكن الوصول إليها. والسؤال: هل يصبح الوصول إلى الحالة q3 ممكناً لو اتجه إليها انتقال من حالة أخرى؟ لو رسمنا حافة من إحدى الحالات q0, q1, q2, q5، لأصبح الوصول إليها ممكناً. أما لو أضفنا عقدة أخرى ورسمنا الانتقال منها…

…فستبقى بالطبع الحالتان q3 و q4 كلتاهما حالتين لا يمكن الوصول إليهما.

تعريف الحالة التي لا يمكن الوصول إليها

نعرّف أولاً الحالة التي يمكن الوصول إليها. ليكن لدينا الأوتومات المنتهي A = ⟨Q, Σ, δ, q0, F⟩. نقول إنّ الحالة q ∈ Q يمكن الوصول إليها إذا وُجدت كلمة w ∈ Σ∗ بحيث

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

والحالة q ∈ Q لا يمكن الوصول إليها إذا لم يكن الوصول إليها ممكناً.

طريقة حذف الحالات التي لا يمكن الوصول إليها

إذا كانت في الأوتومات حالات لا يمكن الوصول إليها، فمن المناسب أن نحذفها. فننشئ أوتوماتاً مكافئاً A′ = ⟨Q′, Σ, δ′, q0, F′⟩ يخلو من الحالات التي لا يمكن الوصول إليها.

ننشئ مجموعة الحالات التي يمكن الوصول إليها بالتكرار. نبدأ بالمجموعة S0 = {q0}، لأنّ الحالة الابتدائية يمكن الوصول إليها بالتأكيد. وننشئ المجموعة التالية كما يلي:

Si={r|δ(q,a)=r لبعض q∈Si−1,a∈Σ}∪Si−1

بعبارة أبسط: المجموعة S0 معطاة دائماً، وننشئ المجموعة S1 بأن نأخذ كل حالات المجموعة S0 ونبحث عن كل الحالات التي تتجه إليها الانتقالات لكل رموز Σ. ثم نأخذ اتحاد هذه الحالات مع المجموعة الأصلية S0. وبالطريقة نفسها نجد المجموعة S2 وما بعدها. ومن الواضح أنّ Si − 1 ⊆ Si.

ونحصل بعد ذلك على مجموعة الحالات التي يمكن الوصول إليها كما يلي:

⋃i=1∞Si

قد يبدو غريباً أن نحاول أخذ اتحاد عدد لا نهائي من المجموعات Si، لكنّ الأوتومات لا يحتوي إلا على عدد منتهٍ من الحالات. وهذا يعني أنّ المجموعات Sj و Sj + 1 وكل ما بعدها ستصبح متساوية عند لحظة ما، ولذلك يمكن أن نحصل على مجموعة منتهية من الحالات حتى بعد أخذ اتحاد عدد لا نهائي من المجموعات.

لنعد إلى الأوتومات

ولنحاول أن نجد مجموعة الحالات التي يمكن الوصول إليها. نبدأ بوضع المساواة الأساسية

S0={q0}

نحسب الآن المجموعة S1. فعلينا أن نجد كل الانتقالات من الحالة q0 ونضيف حالاتها الهدف إلى المجموعة S0. وبما أنّ q0 → a q1 و q0 → bq2، فستحتوي المجموعة S1 زيادة على ذلك على الحالتين q1 و q2:

S1={q0,q1,q2}

ثم ننشئ المجموعة S2. ننظر إلى كل الحالات التي يمكننا الوصول إليها من الحالات q0, q1, q2. والحالة الجديدة الوحيدة هي q5 التي يمكننا الوصول إليها من الحالة q1:

S2={q0,q1,q2,q5}

ثم ننشئ المجموعة S3. هل يمكننا أن نصل من الحالات q0, q1, q2, q5 إلى حالة جديدة؟ لا يمكننا، ولذلك تحتوي المجموعة S3 على العناصر نفسها التي في S2:

S3={q0,q1,q2,q5}

وبما أنّ S2 = S3، فإنّ S3 = S4 = S5 = … أيضاً. فإذا أخذنا اتحاد كل المجموعات Si حصلنا على المجموعة S2، لأنه لن يُضاف أي عنصر جديد في أي مجموعة لاحقة.

إذن مجموعة الحالات التي يمكن الوصول إليها في الأوتومات هي {q0, q1, q2, q5}. ونحصل على الحالات التي لا يمكن الوصول إليها بأخذ الفرق بين المجموعتين ببساطة:

Q∖⋃i=1∞Si

مجموعة الحالات التي لا يمكن الوصول إليها في أوتوماتنا هي {q3, q4}. نحذف من الأوتومات A كل الحالات التي لا يمكن الوصول إليها، وكل الانتقالات التي تتضمن إحداها. أي نعرّف الأوتومات المكافئ A′ = ⟨Q′, Σ, δ′, q0, F′⟩ الخالي من الحالات التي لا يمكن الوصول إليها، المقابل للأوتومات A = ⟨Q, Σ, δ, q0, F⟩، كما يلي:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

المصادر

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