تقاطع اللغات المنتظمة
لتكن لدينا لغتان منتظمتان L1, L2. سنثبت أنّ تقاطعهما L = L1 ∩ L2 لغة منتظمة أيضاً.
فكرة البرهان
لدينا لغتان منتظمتان L1 و L2، ونريد أن نثبت أنّ تقاطعهما L1 ∩ L2 لغة منتظمة أيضاً. وبما أنّ L1 و L2 لغتان منتظمتان، فيوجد أوتوماتان منتهيان A1 و A2 يقبلان اللغتين L1 و L2، أي L(A1) = L1 و L(A2) = L2. سننشئ بعد ذلك أوتوماتاً منتهياً A يقبل اللغة L1 ∩ L2، وبذلك نثبت أنّ اللغة L1 ∩ L2 منتظمة.
تنتمي الكلمة إلى تقاطع اللغتين إذا انتمت إلى اللغة L1 وإلى اللغة L2 معاً. أي يجب أن يقبلها الأوتومات A1 والأوتومات A2 معاً. فنستعمل الفكرة نفسها التي استعملناها في اتحاد اللغات المنتظمة، ونغيّر فقط مجموعة الحالات النهائية.
الصياغة الصورية للطريقة
لدينا أوتوماتان،
ننشئ الأوتومات A = ⟨Q, Σ, δ, q, F⟩ الذي يقبل اللغة L(A1) ∩ L(A2)، حيث
- Q = Q1 × Q2
- Σ= Σ1 ∩ Σ2
- q = ⟨q0, p0⟩
- F = F1 × F2
وتحقق دالة الانتقال δ العلاقة الآتية:
مثال على التقاطع
ليكن لدينا الأوتومات A1 الآتي الذي يقبل كل الكلمات التي تحتوي على عدد زوجي من الآحاد:
والأوتومات A2 الذي يقبل الكلمات التي تحتوي على عدد فردي من الأصفار:
ننشئ الأوتومات الذي يقبل تقاطع هاتين اللغتين. مجموعة حالات هذا الأوتومات على الصورة Q = Q1 × Q2، والحالة الابتدائية هي الحالة ⟨q0, p0⟩، والحالات النهائية هي F1 × F2:
ثم نكمل الانتقالات بحيث يكون δ(⟨q,p⟩, a) = ⟨δ1(q, a), δ2(p, a)⟩:
في هذا الأوتومات مثلاً انتقال من الحالة ⟨q0, p0⟩ للرمز 0 إلى الحالة ⟨q0,p1⟩. ومعنى ذلك أنّ للأوتومات A1 انتقالاً من الحالة q0 للرمز 0 يعود إلى الحالة q0، وأنّ للأوتومات A2 انتقالاً للرمز 0 من الحالة p0 إلى الحالة p1.
ويمكننا أن نجرّب الأوتومات. ينبغي أن يقبل كلمات مثل 110 أو 00000 (تحتوي على عدد زوجي من الآحاد وعدد فردي من الأصفار معاً)، وألّا يقبل كلمات مثل 11 و 111 و 1010.
المصادر
المحتويات: انغلاق اللغات المنتظمة, اتحاد اللغات المنتظمة, تقاطع اللغات المنتظمة, الفرق بين لغتين منتظمتين, مكملة اللغة المنتظمة, ضم اللغات المنتظمة, انغلاق اللغة المنتظمة