اللغات الصورية
اللغة الصورية (formal language) تعميم لمفهوم اللغة الذي نعرفه من الحياة اليومية.
المفاهيم الأساسية
يمكننا في البداية أن نتخيل اللغة الصورية لغةً عادية، كاللغة العربية مثلاً. فممّ تتكوّن هذه اللغة؟ تتكوّن من كلمات نربطها بعد ذلك في جمل. لن تهمنا الجمل هنا، بل الكلمات وحدها. وممّ تتكوّن الكلمات؟ من حروف الأبجدية. لذلك نبدأ بالأبجدية.
الأبجدية (alphabet) هي أي مجموعة غير خالية. ونسمّي عناصر الأبجدية رموزاً. فإذا كان الحديث عن العربية، فالأبجدية هي الحروف العربية المعروفة مع أشكال الهمزة والتاء المربوطة والألف المقصورة. وإذا أردنا أن نصف الأعداد بدلاً من العربية، لكانت في الأبجدية الأرقام العشرة كلها. ونرمز للأبجدية عادةً بالرمز Σ.
الكلمة (word)، وتُسمّى أيضاً السلسلة (string)، هي متتالية منتهية من رموز أبجدية ما Σ. فإذا كانت لدينا مثلاً الأبجدية Σ= {a,b,c,d,e,…, z}، فإنّ المتتالية «ahoj» أو «dobrman» كلمة، أما «café» فليست كلمة (لا يوجد في الأبجدية الحرف «é»)، وكذلك «Ahmad» (لا يوجد الحرف «A») و»dobry den» (لا توجد المسافة). وطول الكلمة هو عدد الرموز التي تتكوّن منها.
ضم الكلمات: إذا كانت لدينا كلمتان a = a1a2… an و b = b1b2… bm، فإنّ ضمّهما (concatenation) يعطي الكلمة ab = a1a2… anb1b2… bm. مثال: ضم الكلمتين «ahoj» و»dobrman» يعطي الكلمة «ahojdobrman». ونرمز للضم إما بدائرة صغيرة، أي a ∘ b، أو لا نرمز له بشيء، فنكتب الكلمتين متجاورتين دون رمز خاص للضم.
الكلمة الفارغة نرمز لها بالرمز ε، وهي الكلمة التي طولها صفر. فإذا ضممنا الكلمة a = a1… an إلى الكلمة الفارغة ε، حصلنا على الكلمة a نفسها، أي a ∘ ε = a.
انغلاق الأبجدية Σ هو مجموعة كل الكلمات التي نستطيع تكوينها من الأبجدية Σ، ومنها الكلمة الفارغة. ونرمز للانغلاق بالرمز Σ∗. فإذا كانت لدينا الأبجدية الثنائية Σ= {0, 1}، فإنّ
ونستعمل أحياناً أيضاً الانغلاق الموجب للأبجدية، وهو كذلك كل الكلمات التي نستطيع تكوينها من الأبجدية ما عدا الكلمة الفارغة. نرمز للانغلاق الموجب بالرمز Σ+، ويكون Σ+ = Σ∗ ∖ {ε}.
أمثلة على الأبجديات
-
لنعد إلى مثال اللغة العربية. كل كلمة عربية نجدها في انغلاق الأبجدية التي تضم الحروف العربية بأشكالها كلها (وربما علامات التشكيل أيضاً). وإذا أضفنا إلى هذه الأبجدية المسافة وعلامات الترقيم (الفاصلة والنقطة وعلامة التعجب وعلامة الاستفهام…)، حصلنا بالانغلاق على كل الجمل التي نستطيع تكوينها في العربية. وبالطبع سيضم هذا الانغلاق أيضاً جملاً من نوع «سشيبل كمنتب ؤرلاىةو بيس!!!:؟؟: ::!؟:؟:يبس»، وهي جمل لا معنى لها.
-
إذا ضمّت أبجديتنا كل الأرقام Σ= {0, 1, …, 9}، فسيضم الانغلاق كل الأعداد الطبيعية، وأشياء أخرى زيادة عليها. ففيه أيضاً أعداد تبدأ بالصفر، مثل 00054، والصفر وحده، وفيه كذلك الكلمة الفارغة التي ليست عدداً بالطبع.
-
يجب ألّا تكون الأبجدية خالية، ولذلك تحتوي أصغر أبجدية على رمز واحد على الأقل. فمن الأبجدية Σ= {!} مثلاً نحصل على الانغلاق Σ∗ = {ε, !, !!, !!!, !!!!, …}، أي على مجموعة كلمات يوجد فيها لكل n ∈ ℕ0 كلمة مكوّنة من n علامة تعجب، ولا توجد فيها أي كلمة أخرى.
-
لتكن Σ= {qw,c}. هذه أبجدية غريبة جداً، لأنها تحتوي على الكلمة qw. لا يُستعمل هذا الترميز عادةً لأنه مربك وغريب، لكن يمكننا أن نتخيل أننا ألصقنا الحرفين «q» و»w» معاً فصارا رمزاً واحداً. عندئذٍ نرى الكلمة «qw» رمزاً واحداً هو «qw». فإذا كوّنّا من هذا الرمز الكلمة «qwcqw»، كان طول هذه الكلمة ثلاثة، لأنها مكوّنة من الرموز «qw» و»c» و»qw». لا نصادف مثل هذه الأبجديات كثيراً، لكن توجد حالات نحتاج فيها إلى رموز مكوّنة من عدة رموز.
تعريف اللغة الصورية
اللغة (الصورية) على الأبجدية Σ هي أي مجموعة جزئية من Σ∗. فاللغة L على الأبجدية Σ تحقق L ⊆ Σ∗. وهذه أمثلة على اللغات:
-
عرّفنا في الجزء السابق أبجدية الأرقام Σ= {0, 1, …, 9}. وانغلاقها هو كل الكلمات المكوّنة من الأرقام وحدها. فإذا أضفنا قاعدة تنص على أنّ الكلمة لا تبدأ بالصفر ولا تكون فارغة، حصلنا على مجموعة الأعداد الطبيعية ℕ. ولدينا العلاقة ℕ ⊆ Σ∗، إذن ℕ لغة على الأبجدية Σ.
-
يمكننا أن نضيف إلى مجموعة الأرقام السابقة إشارة الطرح «-»، فتصبح Σ= {0, 1, …, 9, −}. وانغلاقها هو كل الكلمات المكوّنة من الأرقام أو من إشارة الطرح. وهذا يعني أنّ الانغلاق يضم أيضاً كلمات مثل «12-84-» أو «1-5-8» أو «-». ونكوّن لغة الأعداد الصحيحة ℤ بإضافة ثلاث قواعد:
- إشارة الطرح إما ألّا تظهر في الكلمة أبداً، وإما أن تظهر في بدايتها.
- لا يكون الرقم الأول في الكلمة صفراً، إلا في الكلمة «0».
- يجب أن تحتوي كل كلمة على رقم واحد على الأقل.
تصف هذه المجموعة مجموعة الأعداد الصحيحة، وهي مجموعة جزئية من المجموعة Σ∗، أي أنها لغة على الأبجدية Σ.
-
لتكن Σ= {0, 1}. انغلاقها إذن هو كل الكلمات المكوّنة من الأصفار والآحاد. ويمكننا أن نعرّف اللغة L على هذه الأبجدية مثلاً بأنها مجموعة كل الكلمات التي تحتوي على ثلاثة آحاد بالضبط. ويمكننا أن نكون أكثر إبداعاً فنقول إنّ اللغة L هي مجموعة كل الكلمات التي تمثّل ملفاً صالحاً بصيغة docx (أي ما يخرج من برنامج Word).
-
لنبقَ مع الأبجدية الثنائية Σ= {0, 1}. يمكن تحويل أي سلسلة من المحارف (المحارف العادية الموجودة على لوحة المفاتيح) إلى الصورة الثنائية، أي إلى أصفار وآحاد، ثم إعادتها كما كانت، مثلاً باستعمال جدول آسكي (أو بدقة أكبر: جدول آسكي يحوّل المحارف إلى أعداد، والأعداد في النظام العشري يمكن تحويلها إلى أعداد في النظام الثنائي). وبذلك يمكننا أن نعرّف لغة كل الكلمات التي تمثّل عنوان بريد إلكتروني صالحاً، وتبقى لغة على الأبجدية الثنائية.
ضم اللغات: يمكننا أن نضم اللغات أيضاً. والتعريف يشبه تعريف الضرب الديكارتي للمجموعات. لتكن لدينا لغتان L1 و L2. بضمّهما L1 ∘ L2 نحصل على لغة جديدة نعرّفها كما يلي:
أي نأخذ كل كلمات اللغة L1 ونضم كلاً منها إلى كل كلمات اللغة L2. مثال: لتكن
عندئذٍ يكون:
استعملنا حتى الآن في وصف اللغات لغةً عادية، أي وصفنا بالكلمات شكل اللغة المطلوبة. لكنّ هذا غير عملي إطلاقاً، ولذلك نلجأ إلى طرق أكثر صورية لتعريف اللغة. وأولى هذه الطرق القواعد النحوية (grammar).