✖

تحويل الأوتومات إلى تعبير نمطي

سنعرض كيف نحوّل أي أوتومات منتهٍ إلى تعبير نمطي.

وصف الخوارزمية

في المدخلات أوتومات NFA ما A. نحوّله أولاً إلى GNFA. وفي المرحلة الثانية نحذف في كل خطوة حالة واحدة، ونعدّل دالة الانتقال تعديلاً صحيحاً، ونكرر ذلك حتى لا تبقى إلا حالتان: الحالة الابتدائية والحالة النهائية. وبينهما حافة تحمل تعبيراً نمطياً هو ناتج الخوارزمية كلها. فالطريقة كلها تقوم أساساً على حذف حالة ثم إصلاح الأوتومات بحيث نحصل على أوتومات مكافئ.

حذف حالة واحدة

نوضّح طريقة حذف حالة واحدة بمثال بسيط. لنفرض أنّ جزءاً من أوتوماتنا كما يلي:

حيث Ri تعابير نمطية ما. فكيف يصبح الأوتومات لو حذفنا الحالة qr؟ يمكننا أن نتخيل أننا في الحالة qi، ونسأل: ما كل الكلمات التي نستطيع توليدها في هذا الجزء؟ إذا انتقلنا من الحالة qi مباشرة إلى الحالة qj، فهي كل الكلمات التي تطابق التعبير النمطي R4.

أما إذا انتقلنا إلى الحالة qr، فيمكننا أن نولّد كلمات على الصورة R1. لكن يمكننا في الحالة qr أن ندور في الحلقة للتعبير النمطي R2، أي يمكننا في الواقع أن نولّد كلمات على الصورة R1∘(R2∗). وبما أننا نستطيع أيضاً أن ننتقل من الحالة qr إلى الحالة qj، فنضيف التعبير النمطي R3. فنحصل بهذا الطريق إجمالاً على كلمات على الصورة R1∘(R2∗)∘R3.

نعرف الآن أنّ هذا الجزء من الأوتومات يمكن أن يولّد كلمات على الصورة R4 أو على الصورة R1∘(R2∗)∘R3. ويمكننا بالطبع أن نكتب ذلك في صورة التعبير النمطي (R4)|(R1∘(R2∗)∘R3).

ويمكننا الآن بسهولة أن نحذف الحالة qr، فلا تبقى إلا الحالتان qi و qj، ونكتب بدلاً من R4 التعبير النمطي الذي حسبناه للتو:

ونطبّق هذه الطريقة على كل حافة من كل حالة qi إلى حالة ما qj، ومنها الحلقات، أي الحالة التي يكون فيها qi = qj.

وبعد حذف حالة واحدة نحصل على أوتومات مكافئ، أي أوتومات يتعرّف على اللغة نفسها.

الخوارزمية كاملة

في المدخلات NFA هو A = ⟨Q, Σ, δ, q0, F⟩.

  1. نحوّل NFA A إلى GNFA Z = ⟨Q′, Σ, δ′, q0′, qf′⟩. ونرمز بعد ذلك بالحرف k لعدد الحالات في Z.
  2. إذا كان k = 2، تنتهي الخوارزمية، ويكون على الحافة بين الحالة الابتدائية والحالة النهائية التعبير النمطي الناتج.
  3. إذا كان k>2، نختار أي حالة qr تختلف عن الحالة الابتدائية والحالة النهائية، أي qr ≠ q0′ و qr ≠ qf′. ثم ننشئ GNFA جديداً Z′ = ⟨Q′′, Σ, δ′′,q0′,qf′⟩ يحقق: Q′′=Q′∖{qr} ولكل qi ∈ Q′′ ∖ {qf′} ولكل qj ∈ Q′′ ∖ {q0′} ليكن δ′′(qi,qj)=(R4)|(R1(R2∗)R3), حيث R1 = δ′(qi,qr)، R2 = δ′(qr,qr)، R3 = δ′(qr, qj)، R4 = δ′(qi, qj). ثم نتابع بالخطوة 2.

مثال على التحويل

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

نحوّله أولاً إلى GNFA (ولن نرسم انتقالات ∅ غير الضرورية):

نطبّق الآن الجزء الثاني من الخوارزمية ونحذف إحدى العقد. نبدأ بالعقدة q2. نحذف العقدة q2 ونضيف انتقالاً من الحالة q1 إلى الحالة qf. ونسم هذا الانتقال بالتعبير b(a|b)∗، لأننا ننتقل من العقدة q1 إلى الحالة q2 بالكلمات التي على الصورة b، ثم يمكننا أن ندور في الحلقة للتعبير a|b، فنحصل على (a|b)∗، وأخيراً ننتقل بقاعدة إبسيلون إلى qf. ولدينا b(a|b)∗ϵ = b(a|b)∗. فنحصل على الأوتومات:

يبقى أن نحذف الحالة الأخيرة، q1. نضيف حافة من الحالة qs إلى الحالة qf. فبأي تعبير نسمها؟ نصل إلى الحالة q1 بقاعدة إبسيلون، ويمكننا أن نهمل هذه القاعدة مباشرة. ثم يمكننا أن ندور في الحلقة للرمز a، فنحصل على التعبير النمطي a∗. وأخيراً ننتقل عبر الحافة إلى qf، فنضم التعبير أيضاً إلى b(a|b)∗. فنسم الحافة بالتعبير النمطي a∗ b(a|b)∗.

لم يبقَ في الأوتومات إلا حالتان، فتنتهي الخوارزمية. وعلى الحافة التعبير النمطي الناتج.

المصادر

المحتويات: التعابير النمطية, تحويل التعبير النمطي إلى أوتومات, الأوتومات المنتهي غير الحتمي المعمم, تحويل الأوتومات إلى تعبير نمطي