✖

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

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

مثال تمهيدي

قبل أن نصف الخوارزمية نفسها، نوضّح بمثال ما نريد الوصول إليه. ليكن لدينا التعبير النمطي الآتي: a(b|c)x∗. نصف بالكلمات اللغة التي يولّدها هذا التعبير النمطي بأنها الكلمات التي تبدأ بالحرف «a»، ثم يتبعه إما الحرف «b» وإما الحرف «c»، ثم يتبع ذلك أي عدد من الحروف «x». فهل نستطيع أن ننشئ أوتوماتاً يقبل هذه اللغة؟ نعم بالتأكيد، وهذا هو:

من الواضح أنّ هذا الأوتومات يقبل اللغة نفسها. فيطرح السؤال نفسه: هل يوجد لكل تعبير نمطي أوتومات يقبل اللغة التي يولّدها؟ والجواب: نعم.

وصف خوارزمية تحويل التعبير النمطي إلى أوتومات

نفرض أنّ في المدخلات التعبير النمطي R. ونعرف من الجزء السابق عن التعابير النمطية أنّ التعبير النمطي يمكن أن يكون على ست صور مختلفة. فنميّز ست حالات:

  1. R = a لرمز ما a ∈ Σ. أي أنّ التعبير النمطي رمز واحد فقط من الأبجدية Σ التي نعمل عليها. والأوتومات الذي يقبل الرمز الواحد a كما يلي:

  2. R = ϵ، الكلمة الفارغة. والأوتومات الذي يقبل الكلمة الفارغة كما يلي:

  3. R = ∅، التعبير النمطي الذي يولّد اللغة الخالية. والأوتومات الذي يتعرّف على هذه اللغة هو الآتي:

  4. R = R1 ∪ R2، حيث R1, R2 تعبيران نمطيان. نعرف أنّ اتحاد اللغات المنتظمة لغة منتظمة أيضاً، وأننا نستطيع أن ننشئ أوتوماتاً يقبل هذه اللغة. بعبارة أخرى: نفرض أنّ لدينا أوتوماتين يتعرّفان على اللغتين اللتين يولّدهما التعبيران R1 و R2، وننشئ بهما أوتوماتاً يقبل اللغة التي يولّدها التعبير R1 ∪ R2. مثال: إذا كان R1 = a و R2 = ϵ، فإننا نحصل بهذه الطريقة على الأوتومات الآتي:

  5. R = R1 ∘ R2، حيث R1, R2 تعبيران نمطيان. الحالة مثل الحالة في البند السابق. فضم اللغات المنتظمة لغة منتظمة، ونستطيع أن ننشئ أوتوماتاً يقبل هذه اللغة. فإذا كان R1 = a و R2 = b، كان الضم كما يلي:

  6. R=(R1∗)، حيث R1 تعبير نمطي. نعرف مرة أخرى أنّ انغلاق اللغة المنتظمة لغة منتظمة. فإذا كان R = a∗، كان الأوتومات كما يلي:

وبتطبيق هذه البنود تدريجياً نحوّل التعبير النمطي كله إلى أوتومات منتهٍ.

مثال متكامل

لنحاول تحويل التعبير النمطي (a|bc)∗. نحصل تدريجياً على الأوتومات الآتية:

يقبل هذا الأوتومات الناتج اللغة التي يولّدها التعبير النمطي (a|bc)∗. وبالطبع هذا الأوتومات معقّد جداً، ولا شك أنه يوجد أوتومات أبسط بكثير يقبل اللغة نفسها. فيمكننا أن نستعمل خوارزمية تحويل NFA إلى DFA، ثم نجري تصغير الأوتومات.

المصادر

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