✖

الفرق بين لغتين منتظمتين

لتكن لدينا لغتان منتظمتان L1, L2. سنثبت أنّ الفرق بينهما L = L1 ∖ L2 لغة منتظمة أيضاً.

الفكرة

في الحقيقة لا يوجد الكثير مما يحتاج إلى إثبات. فالفرق بين مجموعتين يحقق العلاقة الآتية:

L1∖L2=L1∩L2′,

حيث L2′ مكملة اللغة L2. ونعرف من فصلَي تقاطع اللغات المنتظمة ومكملة اللغة المنتظمة أنّ اللغات المنتظمة مغلقة بالنسبة إلى هاتين العمليتين. أي نستطيع أن ننشئ أوتوماتاً يقبل تقاطع لغتين وأوتوماتاً يقبل مكملة لغة. فيمكننا أن نستعمل هذين الأوتوماتين لإنشاء أوتومات يقبل اللغة L1 ∩ L2′، وهي نفسها اللغة L1 ∖ L2.

مثال على الفرق

ليكن لدينا الأوتومات A1 الآتي الذي يقبل كل الكلمات التي تحتوي على عدد زوجي من الآحاد:

والأوتومات A2 الذي يقبل الكلمات التي تحتوي على عدد فردي من الأصفار:

ننشئ الأوتومات الذي يقبل الفرق بين هاتين اللغتين. نحتاج إذن إلى الأوتومات A2′ المكمّل للأوتومات A2. فنبدّل فقط الحالات النهائية بالحالات غير النهائية:

ولم يبقَ إلا أن ننشئ الأوتومات A الذي يقبل تقاطع اللغتين L(A1) و L(A2′):

المصادر

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