Cours: Automates d’états finis & expressions régulières

يقدم هذا المستعرض المفصل لمفهوم automates الحالات المحددة (AFD و AFND) والتعبيرات العادية كوسيلة لوصف اللغات المنتظمة. يبدأ بتعريف automate الحالات المحددة كمجموعة من الحالات، أبجدية، دالة انتقال، حالات ابتدائية ونهائية، مع توضيح التمثيل بالرسم البياني المسمى. يوضح كيف يتم حساب قبول كلمة من خلال تتبع الانتقالات بدءًا من الحالة الابتدائية وصولًا إلى حالة نهائية. يفرق بين automates المحددة (حيث لا يوجد أكثر من انتقال واحد لكل حالة ورمز) والغير محددة (حيث قد توجد عدة انتقالات أو انتقال ε). يقدم أمثلة عملية على بناء automates للغات بسيطة مثل تلك التي تحتوي على عدد زوجي من الرموز 0 أو تبدأ بـ01. يشرح نظرية كليني التي تؤكد أن كل لغة منتظمة يمكن تمثيلها بواسطة automate غير محدد ومن ثم تحويلها إلى automate محدد مكافئ. يتناول أيضًا تقليل automates المحددة عبر تقسيم الحالات إلى مجموعات غير قابلة للتمييز وإزالة الحالات الميتة وغير القابلة للوصول. يختم بخصائص اللغات المنتظمة مثل الإغلاق تحت الاتحاد، التقطيع،closure Kleene، والاختلاف، مع أمثلة توضيحية. يهدف المستعرض إلى تمكين الطالب من بناء وتحليل automates والتعبيرات العادية وفهم أهميتها في مجالات مثل تحليل المترجمات ومعالجة النصوص.