✖

التعابير النمطية

التعبير النمطي (regular expression)، ويُسمّى أيضاً التعبير المنتظم، سلسلة نصية تمكّننا من وصف مجموعة من الكلمات. ويمكننا أن نفهم التعابير النمطية أيضاً على أنها طريقة بسيطة لوصف الأوتومات المنتهي.

ما التعبير النمطي

نستعمل في الحساب رموزاً مثل · و + لتكوين عبارة مثل (2 + 3) · 4، وبحساب قيمة هذه العبارة نحصل على عدد. أما التعبير النمطي فهو متتالية من المحارف وبعض الرموز الخاصة، مثل a(x ∪ y)، وقيمته لغة (صورية). فناتج العبارة (2 + 3) · 4 هو العدد 20، وناتج التعبير النمطي a(x ∪ y) هو مجموعة الكلمتين «ax» و»ay».

فكيف نحسب قيمة التعبير النمطي السابق a(x ∪ y)؟ كل حرف هو في الحقيقة اختصار لمجموعة أحادية العنصر تحتوي على ذلك الحرف، والضرب الخفي هو ضم الكلمات. فيمكننا أن نعيد كتابة التعبير النمطي «كاملاً» كما يلي:

{a}∘({x}∪{y})

ثم نحسب قيمته على النحو الآتي: الاتحاد {x} ∪ {y} يعطينا اللغة {x,y}. وبضم اللغتين {a} و {x,y} نحصل على اللغة {ax, ay}.

تُستعمل التعابير النمطية كثيراً جداً في البرمجة، وفي معظم لغات البرمجة تطبيق لها بشكل ما. فتُستعمل مثلاً للتحقق من أنّ النص الذي أدخله المستخدم يحقق معايير معيّنة (كأن يكون عنوان بريد إلكتروني صالحاً أو تاريخاً صالحاً ونحو ذلك)، وكذلك لاستبدال النصوص (فقد نريد مثلاً استبدال كل عناوين URL في نص بروابط قابلة للنقر).

والتطبيقات الفعلية للتعابير النمطية أقوى في الغالب من التعابير النمطية الموصوفة هنا، وتستعمل صياغة مختلفة قليلاً، والأهم أنها أعقد.

تعريف التعبير النمطي

نعرّف التعبير النمطي على أبجدية ما Σ. ونقول إنّ التعبير النمطي هو:

  1. a، حيث a ∈ Σ. أي أنّ رمز الأبجدية وحده تعبير نمطي.
  2. ϵ: الكلمة الفارغة، وتُكتب في البرمجة أيضاً علامتي تنصيص فارغتين «».
  3. ∅: يجب أن يستطيع التعبير النمطي وصف اللغة الخالية أيضاً، فاللغة الخالية تعبير نمطي.
  4. (R1 ∪ R2)، حيث R1, R2 تعبيران نمطيان.
  5. (R1 ∘ R2)، حيث R1, R2 تعبيران نمطيان.
  6. (R∗)، حيث R تعبير نمطي.

ويمكننا أن نستعمل بدلاً من الرمز ∪ في البند 4 رمز الخط العمودي: |. أما الرمز ∘ فلا نحتاج إلى أن نستعمل مكانه شيئاً. فكما أننا لا نكتب عادةً رمز الضرب، أي النقطة الوسطى ·، فإننا لا نكتب عادةً رمز الضم ∘ أيضاً. ولذلك فالتعبيران النمطيان الآتيان متطابقان: a ∘ (b ∪ c) و a(b|c).

فما معنى كل عامل من هذه العوامل؟

  • ∪ أو | يرمز إلى اتحاد اللغات.
  • ∘ يرمز إلى ضم اللغات.
  • ∗ يرمز إلى انغلاق اللغة.

أمثلة:

  • a يرمز إلى اللغة البسيطة {a}.
  • a|b يرمز إلى اللغة المكوّنة من الكلمتين {a, b}.
  • a ∘ b يرمز إلى اللغة {ab}.
  • a(b|c)d يرمز إلى اللغة {abd, acd}.
  • a(b∗) يرمز إلى لغة كل الكلمات التي تبدأ بالحرف «a» ويتبعه أي عدد من الحروف «b».
  • (ab)∗ يرمز إلى لغة كل الكلمات {ϵ, ab, abab, ababab, …}.
  • 0∗10∗ يرمز إلى لغة كل الكلمات الثنائية التي تحتوي على الرقم 1 مرة واحدة فقط. (نلاحظ أنّ الأدق أن نكتب هذا التعبير على الصورة (0∗)1(0∗)، لكن إذا كانت الكتابة مقروءة دون الأقواس أمكننا حذفها.)
  • Σ∗1Σ∗ يرمز إلى لغة كل الكلمات التي تحتوي على الرقم 1 مرة واحدة على الأقل.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ يرمز إلى لغة كل الأعداد الطبيعية.

وسنعرض لاحقاً التكافؤ بين التعابير النمطية والأوتومات المنتهية: فلكل تعبير نمطي قيمته اللغة R يوجد أوتومات منتهٍ A يحقق L(A) = R، والعكس صحيح.

المصادر

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