مادة:اتومات ولغات صورية

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 نبذة

تتحدث المادة بشكل عام عن اللغات الصورية والتي تشمل جميع اللغات التي نتعامل معها، سواءً اللغات الطبيعية (والتي لا نقوم بدراسة النماذج التي توصفها في مادتنا بالتفصيل) أو لغات البرمجة التي نقوم باستخدامها لبناء برامجنا، ولكن المادة تعالج مفاهيم هذه اللغات والنماذج التي توصفها (الأتومات) بشيء من التبسيط وذلك لأنها تعتبر مقدمةً لمواد أخرى أعقد وأهم مثل المترجمات في السنين العليا

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

تتألف المادة من المواضيع والمفردات التالية:

• مقدمة حول الأبجديات واللغات وأهم التصنيفات التي تخضع لها اللغات الصورية.
• اللغات المنتظمة: وهي أبسط أنواع اللغات الصورية، وتحوي المواضيع الجزئية التالية:
  • الأتومات المنتهي الحتمي Deterministic Finite Automata (DFA)
  • الأتومات المنتهي اللاحتمي Non-Deterministic F.A.
  • الأتومات المنتهي اللاحتمي مع E تحرك Epsilon Non-Deterministic Finite Automata
  • التعابير المنتظمة Regular Expressions
• وفي الحقيقة جميع المفردات السابقة هي طرق تستخدم لتوصيف لغة منتظمة واحدة، أي يمكن للغة منتظمة واحدة أن توصف بجميع النماذج الأربعة السابقة كما ويوجد طرق خاصة للتحويل بين هذه النماذج الأربعة وخوارزميات جاهزة نقوم بدراستها أيضاً.

• • الأتومات المنتهي الأصغري: كما علمنا أن الاتومات هو النموذج الذي يوصف لغة منتظمة ما، وبالتأكيد يوجد طريقة ما لجعل هذا الأتومات أصغرياً، أي يحوي عدداً أصغرياً من الحالات (كون الأتومات هو عبارة عن آلة منتهية الحالات تقريباً Finite State Machine).
  • خصائص اللغات المنتظمة: ونقوم بدراسة أهم الخصائص التي تتعلق باللغات المنتظمة، ونتطرق أيضاً لطريقة خاصة من أجل تحديد إن كانت لغة ما منتظمة أو لا، وتسمى هذه الطريقة توطئة الضخ Pumping Lemma. كما ونتعرف على أهم العمليات التي يمكن أن تتم على اللغات المنتظمة والتي تحافظ على انتظامها (كالتقاطع بين لغتين منتظمتين، والاجتماع، ... إلخ)

• اللغات خارج السياق: وهي لغات أكثر شمولاً وأوسع من اللغات المنتظمة، وتضم أيضاً اللغات المنتظمة، وهذه اللغات تستخدم بشكل أساسي من أجل وضع القواعد الأساسية للمترجم في لغات البرمجة، وتشمل هذه اللغات الموضوعات الجزئية التالية:
  • القواعد الخارج السياق Context Free Grammars
  • الاشتقاق اليميني واليساري Derivation
  • شجرة الاشتقاق والقواعد الغامضة
  • تبسيط القواعد خارج السياق: ويوجد العديد من الطرق التي تستخدم لاختصار وتبسيط القواعد خارج السياق ويتم التعرف عليها جميعها بشيء من التفصيل
  • الصيغة المعيارية لتشومسكي Chomsky Normal Form
  • الصيغة المعيارية لغريباخ Greibach Normal Form
  • توطئة الضخ في اللغات خارج السياق : وهنا من أجل التعرف إن كانت لغة ما خارج السياق أم لا
  • خصائص اللغات خارج السياق: ونتعرف هنا على أهم العمليات التي يمكن أن نقوم بها على اللغات خارج السياق وتبقيها خارج السياق (اجتماع لغتين أو تقاطع لغتين ... إلخ)
  • خوارزمية CYK: وهذه الخوارزمية تقوم بالتأكد من كون كلمة ما تنتمي إلى لغة خارج السياق أم لا، وتهم كثيراً في التعرف على المفردات التي تنتمي إلى لغة برمجة ما مثلاً، هذا مع العلم أنه يوجد خوارزميات أخرى ولكن في مادتنا لا نتعرف سوى على هذه الخوارزمية.
  • نموذج الأتومات بمكدس Pushdown Automata: وهذا الأتومات ينمذج ويوصف لغة ما خارج السياق، كما كان لدينا في اللغات المنتظمة نموذج الأتومات المنتهي الذي يوصفها، هنا يوجد هذا الاتومات.
• آلة تيورينغ Turing Machine: وهذه الآلة تستخدم في التعرف على جميع اللغات الصورية تقريباً، أي أنها آلة متعددة الاستخدامات لديها القدرة على الحساب والمنطق، وتعتبر النموذج المبدئي الأول للحاسب الذي ينتشر في أيامنا هذه. (قد لا تعطى بشيء من التفصيل وذلك لضيق الوقت في نهاية العام)

 كتب

• Theory of Automata, Formal Languages and Computation
• Introduction to Automata Theory, Languages, and Computation