✖

اتحاد اللغات المنتظمة

لتكن لدينا لغتان منتظمتان 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 منتظمة.

كيف نفعل ذلك؟ بين أيدينا الأوتوماتان المنتهيان A1 و A2 اللذان يقبلان كلاً من اللغتين. ويمكننا أن نقول إنّ الكلمة w تنتمي إلى اللغة L1 ∪ L2 إذا وفقط إذا قبلها أحد الأوتوماتين A1 أو A2 على الأقل.

يمكن أن يعمل الأوتومات A بأن يحاكي، عند المدخل w، حساب الأوتومات A1 للمدخل w. فإذا قبل A1 الكلمة w، قبل A الكلمة w أيضاً. وإذا رفض A1 الكلمة w، حاول A أن يحاكي حساب A2 للمدخل w. فإذا قبل A2 الكلمة w، قبل A أيضاً الكلمة w، وإلا رفضها.

يبقى أن نصوغ صورياً معنى أن «يحاكي» الأوتومات A حساب أوتومات آخر.

الصياغة الصورية للإنشاء الحتمي

لدينا لغتان منتظمتان L1 و L2 يقبلهما الأوتوماتان المنتهيان

A1=⟨Q1,Σ1,δ1,q1,F1⟩A2=⟨Q2,Σ2,δ2,q2,F2⟩.

ننشئ الأوتومات المنتهي A = ⟨Q, Σ, δ, q, F⟩ الذي يقبل اللغة L = L1 ∪ L2. ونستعمل فكرة محاكاة الأوتوماتين A1, A2. لنتخيل أنّ في المدخلات الكلمة w = w1w2… wn، وأننا سنحاكي في آن واحد سير الأوتوماتين A1 و A2 للكلمة w. التشكيل الابتدائي للأوتومات A1 هو ⟨q1, w1w2… wn⟩، والتشكيل الابتدائي للأوتومات A2 هو ⟨q2, w1w2… wn⟩. ننفّذ الآن في كل أوتومات خطوة حسابية، فنصل إلى التشكيلين ⟨δ1(q1, w1), w2… wn⟩ و ⟨δ2(q2, w1), w2… wn⟩.

نرى أنّ هذين التشكيلين لا يختلفان إلا في المركّبة الأولى، أما الثانية، وهي الجزء غير المقروء من الكلمة، فهي نفسها دائماً. فلا نحتاج أثناء المحاكاة إلى الاحتفاظ بتشكيلين لأوتوماتين، بل يكفينا تشكيل واحد على الصورة ⟨⟨qi, qj⟩, wl… wn⟩، حيث qi ∈ Q1 و qj ∈ Q2. بعبارة أخرى: يكون للأوتومات A الذي ننشئه التشكيل الابتدائي ⟨⟨q1, q2⟩, w⟩. فالجزء الأول من الثنائي ⟨q1, q2⟩ يمثّل الحالة التي يوجد فيها الأوتومات A1 حالياً، والمركّبة الثانية تمثّل الحالة الحالية للأوتومات A2.

ويمكننا إذن أن نكتب أنّ مجموعة حالات الأوتومات A الذي ننشئه هي Q = Q1 × Q2، أي الضرب الديكارتي لمجموعتي حالات الأوتوماتين السابقين. والفكرة التالية أنّ الحالة الابتدائية للأوتومات A هي ⟨q1, q2⟩، وإذا انتقل الأوتومات A1 بالرمز w1 إلى الحالة qi، وانتقل الأوتومات A2 بالرمز w1 إلى الحالة qj، فإنّ الأوتومات A ينتقل بالرمز w1 إلى الحالة ⟨qi, qj⟩.

نكتب دالة الانتقال δ كما يلي (ونفرض هنا أننا حالياً في الحالتين qi و qj):

δ(⟨qi,qj⟩,w)=⟨δ1(qi,w),δ2(qj,w)⟩

لم يبقَ إلا بعض التفاصيل. فالأبجدية هي Σ= Σ1 ∪ Σ2، والحالة الابتدائية هي q = ⟨q1, q2⟩. أما الحالات النهائية فهي كل الثنائيات ⟨qi, qj⟩ التي يتحقق فيها إما qi ∈ F1 وإما qj ∈ F2.

توضيح الطريقة بمثال

ليكن لدينا أوتوماتان. الأول هو الأوتومات A1 الذي يقبل كل الكلمات (ومنها الكلمة الفارغة) التي تتناوب فيها الأصفار والآحاد، أي الكلمات التي على الصورة 01 و 0101 و 010101 و…

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

اتحاد هاتين اللغتين هو الكلمات التي إما تحتوي على صفر وإما تكون على الصورة 01 و 0101 و… ننشئ الآن الأوتومات المنتهي A = ⟨Q, Σ, δ, q, F⟩ الذي يقبل هذه اللغة الناتجة عن الاتحاد. ونبدأ بحالات هذا الأوتومات الجديد A، وهي الضرب الديكارتي لحالات الأوتومات الأول وحالات الأوتومات الثاني:

Q=Q1×Q2={⟨q0,p0⟩,⟨q0,p1⟩,⟨q1,p0⟩,⟨q1,p1⟩,⟨q2,p0⟩,⟨q2,p1⟩}

هذه هي الحالات الست للأوتومات A الذي يقبل لغة الاتحاد L(A1) ∪ L(A2). وتظهر في المخطط كما يلي:

لا داعي للقلق من أنّ الحالات هنا مكوّنة من أزواج من الحالات، فذلك يساعدنا فقط على تتبّع ما يحدث في الأوتومات. ويمكن أن تُسمّى الحالات بالطريقة المعتادة q0, …, q5. والحالات النهائية هي الحالات التي تحتوي إما على الحالة q0 وإما على p1، وهما الحالتان النهائيتان في الأوتوماتين الأصليين. والحالة الابتدائية هي ⟨q0, p0⟩.

علينا الآن أن نجد كل الانتقالات. نكتب الجدول الآتي:

01⟨q0,p0⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

ونملأ الجدول تدريجياً. نبحث أولاً عن الحالة التي يؤدي إليها الانتقال من الحالة ⟨q0, p0⟩ بالمدخل 0. فنبحث إلى أين يؤدي الانتقال من الحالة q0 بالمدخل 0 في الأوتومات A1: إنه يؤدي إلى الحالة q1. وفي الأوتومات A2 يؤدي الانتقال من p0 بالصفر إلى الحالة p1. فنكتب في الجدول ⟨q1, p1⟩:

01⟨q0,p0⟩⟨q1,p1⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

وبالمدخل 1 نحصل على: δ1(q0, 1) = q2 في الأوتومات A1، و δ2(p0, 1) = p0 في الأوتومات A2. فنحصل على الحالة ⟨q2, p0⟩.

01⟨q0,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

ونكمل باقي الجدول:

01⟨q0,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q0,p1⟩⟨q1,p1⟩⟨q2,p1⟩⟨q1,p0⟩⟨q2,p1⟩⟨q0,p0⟩⟨q1,p1⟩⟨q2,p1⟩⟨q0,p1⟩⟨q2,p0⟩⟨q2,p1⟩⟨q2,p0⟩⟨q2,p1⟩⟨q2,p1⟩⟨q2,p1⟩

ولم يبقَ إلا أن نكمل رسم المخطط وفق هذا الجدول.

ويمكننا أن نتحقق من أنّ الأوتومات يعمل كما ينبغي. لنحاول قبول الكلمة 0100. يمرّ الأوتومات تباعاً بالحالات

⟨q0,p0⟩,⟨q1,p1⟩,⟨q0,p1⟩,⟨q1,p1⟩,⟨q2,p1⟩

وبما أنّ الحالة ⟨q2, p1⟩ حالة نهائية، فإنّ الأوتومات A يقبل الكلمة 0100. فماذا يحدث لو حاولنا قبول الكلمة 0100 بالأوتوماتين A1 و A2؟ يمرّ الأوتومات A1 تباعاً بالحالات الآتية:

q0,q1,q0,q1,q2

انتهى الأوتومات في الحالة q2 وهي ليست نهائية، إذن لا يقبل الأوتومات A1 هذه الكلمة. وماذا عن الأوتومات A2؟

p0,p1,p1,p1,p1

الحالة p1 نهائية، إذن يقبل الأوتومات A2 الكلمة 0100. نلاحظ أنّ الأوتوماتين A1 و A2 انتهيا في الحالتين q2 و p1، وهذا يتفق مع انتهاء الأوتومات A في الحالة ⟨q2, p1⟩.

الإنشاء بأوتومات غير حتمي

مثال على الإنشاء غير الحتمي

يمكننا أن نثبت أنّ مجموعة اللغات المنتظمة مغلقة بالنسبة إلى الاتحاد بإنشاء أوتومات غير حتمي أيضاً، وهو أبسط بكثير.

لدينا لغتان منتظمتان L1, L2، ونريد أن نثبت أنّ اتحادهما L = L1 ∪ L2 لغة منتظمة أيضاً. وبما أنّ L1, L2 لغتان منتظمتان، فلا بد أن يوجد أوتوماتان A1, A2 يقبلان هاتين اللغتين، أي L(A1) = L1 و L(A2) = L2. وننشئ بهذين الأوتوماتين أوتوماتاً A يقبل اللغة L، أي L(A) = L.

لنفرض أنّ الأوتوماتين المنتهيين A1 و A2 كما يلي:

و

ننشئ الأوتومات الذي يقبل اتحاد اللغتين بأن نضيف حالة ابتدائية جديدة، ونرسم منها انتقالَي إبسيلون إلى الحالتين الابتدائيتين الأصليتين. وهذا كل شيء. ويكون الأوتومات كما يلي:

الصياغة الصورية للإنشاء غير الحتمي

لدينا الأوتوماتان A1 = ⟨Q1, Σ, δ1, q1, F1⟩ و A2 = ⟨Q2, Σ, δ2, q2, F2⟩. ننشئ الأوتومات A = ⟨Q, Σ, δ, q0, F⟩ الذي يقبل اتحاد اللغتين اللتين يقبلهما الأوتوماتان السابقان، أي L(A) = L(A1) ∪ L(A2)، حيث:

  • Q = Q1 ∪ Q2 ∪ {q0}
  • F = F1 ∪ F2

ونعرّف دالة الانتقال δ كما يلي:

δ(q,a)={δ1(q,a)إذاq∈Q1δ2(q,a)إذاq∈Q2{q1,q2}إذاq=q0∧a=ε∅إذاq=q0∧a≠ε

المصادر

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