مكملة اللغة المنتظمة
لدينا لغة منتظمة L. سنثبت أنّ مكملة اللغة L لغة منتظمة أيضاً.
ما المكملة
نقصد بمكملة اللغة L كل الكلمات التي لا تنتمي إلى اللغة L. ونرمز للمكملة بالرمز L'. أي أنّ لدينا للأبجدية Σ:
فمثلاً مكملة لغة الكلمات التي تحتوي على رمز 1 واحد على الأقل هي اللغة التي تضم الكلمات التي لا تحتوي على أي رمز 1.
طريقة الإنشاء
الطريقة بسيطة جداً. لدينا لغة منتظمة L وأوتومات كامل حتمي A = ⟨Q, Σ, δ, q0, F⟩ يقبلها (ويمكن تحويل أي أوتومات منتهٍ إلى أوتومات من هذا النوع). ننشئ الأوتومات A' الذي يقبل L' بأن نبدّل الحالات النهائية بالحالات غير النهائية: A' = ⟨Q, Σ, δ, q0, Q ∖ F⟩. وهذا كل شيء.
مثال على المكملة
ليكن لدينا الأوتومات الآتي:
ويكون الأوتومات الذي يقبل مكملة اللغة كما في الشكل الآتي:
المصادر
المحتويات: انغلاق اللغات المنتظمة, اتحاد اللغات المنتظمة, تقاطع اللغات المنتظمة, الفرق بين لغتين منتظمتين, مكملة اللغة المنتظمة, ضم اللغات المنتظمة, انغلاق اللغة المنتظمة