ضم اللغات المنتظمة
لتكن لدينا لغتان منتظمتان L1, L2. سنثبت أنّ ضمّهما (concatenation) L = L1 ∘ L2 لغة منتظمة أيضاً.
ما الضم
بضم الكلمتين «010» و»1111» نحصل على الكلمة «0101111». وبضم اللغات نحصل على لغة جديدة ننشئها بأن نضم كل كلمة من إحدى اللغتين إلى كل كلمة من اللغة الأخرى. ونرمز لضم كلمتين ولضم لغتين بدائرة صغيرة: ∘. وعندئذٍ يمكننا أن نعرّف ضم اللغتين L1 و L2 كما يلي:
فكرة البرهان
لدينا لغتان منتظمتان L1, L2، وأوتوماتان يقبلان هاتين اللغتين:
ننشئ أوتوماتاً غير حتمي A = ⟨Q, Σ, δ, q, F⟩ «يحتوي في داخله» على الأوتوماتين A1 و A2. والفكرة الأساسية أن نبدأ قبول الكلمة بالأوتومات A1، فإذا وصل الأوتومات A1 إلى حالة نهائية، حاولنا أن نقبل الجزء الباقي من الكلمة بالأوتومات A2. فإذا قبل هذا الأوتومات أيضاً ذلك الجزء من الكلمة، قبل الأوتومات A الكلمة.
مثال على الضم
ليكن لدينا الأوتومات A1 الآتي الذي يقبل الكلمات غير الفارغة المكوّنة من الأصفار وحدها، والكلمات المكوّنة من الرقم 1 تتبعه أصفار فقط (1، 10، 100، …):
وليكن لدينا أيضاً الأوتومات A2 الآتي الذي يقبل الكلمات التي تنتهي بالسلسلة 01:
نصل الأوتوماتين بأن نضيف انتقالات إبسيلون من كل الحالات النهائية للأوتومات A1 إلى الحالة الابتدائية للأوتومات A2، ثم نجعل الحالات النهائية للأوتومات A1 حالات عادية. وتكون الحالة الابتدائية للأوتومات الجديد كله هي الحالة الابتدائية للأوتومات A1:
كيف يعمل هذا الأوتومات؟ نبدأ بمحاكاة عمل الأوتومات A1. فإذا انتقلنا إلى الحالة q1 أو q2، وكانتا حالتين نهائيتين سابقاً، عرفنا أنّ الأوتومات A1 يقبل جزءاً من هذه الكلمة. ولكي تكون الكلمة كلها من اللغة L1 ∘ L2، يجب أن يقبل الأوتومات الثاني A2 الجزء الباقي منها، ولذلك تخرج من كل الحالات النهائية السابقة انتقالات إبسيلون إلى الحالة الابتدائية الأصلية للأوتومات A2.
لنأخذ مثلاً الكلمة 0001. إنها تنتمي إلى ضم اللغتين، لأنه يمكن الحصول عليها بضم الكلمتين 00 ∘ 01. لكن يمكن الحصول عليها أيضاً بضم الكلمتين 0 ∘ 001. ويمكننا أن نحاكي في أوتوماتنا الطريقتين كلتيهما. فيمكن أن يسلك الأوتومات هذا الطريق:
وبهذا الطريق «يقبل» الأوتومات أولاً الجزء 00 من الكلمة ثم الجزء 01. ويمكن أن يسلك أيضاً هذا الطريق:
فالأوتومات «يقبل» أولاً الجزء 0 من الكلمة ثم الجزء 001. وفي الحالتين نصل بالطبع إلى الحالة النهائية p2.
الطريقة الصورية
مرة أخرى: لدينا لغتان منتظمتان L1, L2، وأوتوماتان يقبلان هاتين اللغتين:
ننشئ أوتوماتاً غير حتمي A = ⟨Q, Σ, δ, q, F⟩ يحقق:
- Q = Q1 ∪ Q2 (ونفرض أيضاً أنّ Q1 ∩ Q2 = ∅)
- Σ= Σ1 ∪ Σ2
- q = q0
- F = F2
وننشئ دالة الانتقال δ تدريجياً:
المصادر
المحتويات: انغلاق اللغات المنتظمة, اتحاد اللغات المنتظمة, تقاطع اللغات المنتظمة, الفرق بين لغتين منتظمتين, مكملة اللغة المنتظمة, ضم اللغات المنتظمة, انغلاق اللغة المنتظمة