✖

الأوتومات الكامل

لا يشترط التعريف الأساسي للأوتومات المنتهي أن يخرج من كل حالة انتقال لكل رمز. أما الأوتومات الكامل (complete automaton) فهو أوتومات معرَّفة فيه الانتقالات من كل الحالات لكل رموز أبجدية المدخلات.

طريقة إنشاء الأوتومات الكامل

ليكن لدينا الأوتومات A = ⟨Q, Σ, δ, q0, F⟩ الآتي:

لم يُرسم هنا انتقال من الحالة q0 للحرف «b». فإذا حدث هذا الموقف قلنا إنّ الأوتومات لا يقبل كلمة المدخلات المعطاة. لكن من ناحية الصياغة الصورية قد لا يكون مناسباً أن تبقى دالة الانتقال δ غير معرَّفة لبعض القيم، فهي هنا مثلاً غير معرَّفة عند δ(q0, b).

ويسهل حل ذلك بإنشاء أوتومات مكافئ يزيد بحالة واحدة: تتجه الانتقالات «الناقصة» إلى هذه الحالة، وهي ليست حالة نهائية، وكل المدخلات التالية تبقى تدور فيها. نسمّي هذا الأوتومات الأوتومات الكامل. ويمكن أن يكون الأوتومات المكافئ المعدَّل كما في الشكل الآتي:

أضفنا الحالة qfail، ورسمنا إليها انتقالاً من كل حالة أخرى إذا وفقط إذا لم يكن ذلك الانتقال موجوداً من قبل. هذه الحالة ليست نهائية، وفيها حلقة لكل المدخلات التالية. فحيث كنا نصادف انتقالاً ناقصاً في الأوتومات السابق، لا يوجد هنا أي انتقال ناقص، بل يصل الأوتومات إلى الحالة qfail.

ولذلك يمكننا دائماً، دون فقدان للعمومية، أن نفرض أنّ الأوتومات معرَّفة فيه الانتقالات لكل الأزواج الممكنة من حالة ورمز من الأبجدية.

تعريف الأوتومات الكامل

يحقق الأوتومات الكامل A = ⟨Q, Σ, δ, q0, F⟩ الشرط

∀q∈Q∀a∈Σ∃r∈Q:δ(q,a)=r.

المصادر

المحتويات: الأوتومات المنتهي, الأوتومات الكامل, الأوتومات المنتهي غير الحتمي, محاكاة الأوتومات غير الحتمي, تحويل NFA إلى DFA