✖

مكملة اللغة المنتظمة

لدينا لغة منتظمة L. سنثبت أنّ مكملة اللغة L لغة منتظمة أيضاً.

ما المكملة

نقصد بمكملة اللغة L كل الكلمات التي لا تنتمي إلى اللغة L. ونرمز للمكملة بالرمز L'. أي أنّ لدينا للأبجدية Σ:

L′={w∈Σ∗|w∉L}.

فمثلاً مكملة لغة الكلمات التي تحتوي على رمز 1 واحد على الأقل هي اللغة التي تضم الكلمات التي لا تحتوي على أي رمز 1.

طريقة الإنشاء

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

مثال على المكملة

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

ويكون الأوتومات الذي يقبل مكملة اللغة كما في الشكل الآتي:

المصادر

المحتويات: انغلاق اللغات المنتظمة, اتحاد اللغات المنتظمة, تقاطع اللغات المنتظمة, الفرق بين لغتين منتظمتين, مكملة اللغة المنتظمة, ضم اللغات المنتظمة, انغلاق اللغة المنتظمة