انغلاق اللغة المنتظمة
لدينا لغة منتظمة L. سنثبت أنّ انغلاق اللغة L لغة منتظمة أيضاً.
ما انغلاق اللغة
نرمز لانغلاق اللغة L بالرمز L∗، ويُسمّى أيضاً انغلاق كلين (Kleene closure). ويحتوي الانغلاق على كل الكلمات التي يمكن تكوينها بضم عدد منتهٍ من كلمات اللغة L. ويمكننا أن نعرّف الانغلاق بأنه:
حيث يرمز ∘ إلى عملية الضم. ويحتوي الانغلاق أيضاً على الكلمة الفارغة، أي ϵ.
الطريقة الصورية
نسير بطريقة تشبه كثيراً ما فعلناه في ضم اللغات. لكننا بدلاً من أن نصل أوتوماتين مختلفين، نصل الأوتومات بنفسه، فنرسم انتقالات إبسيلون من الحالات النهائية للأوتومات إلى حالته الابتدائية. غير أنّ الانغلاق يجب أن يحتوي أيضاً على الكلمة الفارغة. فكيف نضمن ذلك؟ يمكننا أن نجعل الحالة الابتدائية حالة نهائية. عندئذٍ يقبل الأوتومات الكلمة الفارغة، لكنه قد يقبل أيضاً كلمة أخرى لا تنتمي إلى الانغلاق. ولذلك ننشئ بدلاً من ذلك حالة ابتدائية جديدة، ونرسم منها انتقال إبسيلون إلى الحالة الابتدائية الأصلية.
لدينا لغة منتظمة L1 وأوتومات يقبل هذه اللغة:
ننشئ أوتوماتاً غير حتمي A = ⟨Q, Σ, δ, qs, F⟩ يحقق:
- Q = Q1 ∪ {qs}
- Σ= Σ1
- F = F1 ∪ {qs}
ونعرّف دالة الانتقال δ كما يلي:
مثال على الانغلاق
ليكن لدينا الأوتومات A1 الآتي الذي يقبل الكلمتين 00 و 11:
انغلاق اللغة L(A1) إذن هو لغة كل الكلمات المكوّنة من الزوجين 00 و 11، مثل 0000 و 110011 و 11110000 وغيرها. وننشئ الأوتومات الذي يقبل هذا الانغلاق بأن نضيف حالة ابتدائية جديدة qs بانتقال إبسيلون إلى الحالة الابتدائية السابقة q0، ونضيف انتقالات إبسيلون من الحالتين q3 و q4 إلى الحالة q0:
ويمكننا أن نتحقق من أنّ هذا الأوتومات يقبل فعلاً الكلمات 0000 و 110011 و 11110000، لكنه لا يقبل مثلاً الكلمة 1010.
المصادر
المحتويات: انغلاق اللغات المنتظمة, اتحاد اللغات المنتظمة, تقاطع اللغات المنتظمة, الفرق بين لغتين منتظمتين, مكملة اللغة المنتظمة, ضم اللغات المنتظمة, انغلاق اللغة المنتظمة