دورة: Automates d’états finis & les expressions régulières – Théories des langages

تقدم هذه الدورة دراسة شاملة للمفاهيم الأساسية في نظرية اللغات والحسابات، مع التركيز على automates d'états finis (الآتات ذات الحالات المحدودة) والتعبيرات المنتظمة. تبدأ بتعريف automate كخمسية (Q, Σ, δ, I, F) وتوضيح تمثيله بالرسم البياني الموجه وحساب الانتقالات. ثم تميز بين automates المحددة (AFD) حيث لا توجد أكثر من-transition واحدة لكل حالة ورمز، والآتات غير المحددة (AFND) التي قد تحتوي على عدة transitions أو transitions ε. يُقدّم Théorيم كلين الذي يثبت أن كل لغة منتظمة يمكن وصفها بتعبير منتظم وبالعكس، مع أمثلة بناء automates من التعبيرات المنتظمة والعكس. يُناقش théorيم تكافؤ automates غير المحددة والمحددة عبر طريقة بناء automates المحددة من خلال مجموعات الحالات (طريقة بناء subsets). بعد ذلك، يُشرح عملية تقليل automates المحددة إلى أبسط شكل باستخدام تقسيم الحالات وإزالة الحالات غير الوصولية والعديمة الفائدة. أخيراً، تُستعرض خواص اللغات المنتظمة مثل الإغلاق تحت الاتحاد، التقطيع، التكملة، والConcatenation، مع أمثلة توضح كيف تبقى اللغات الناتجة منتظمة. تُبرز الدورة أهمية هذه المفاهيم في تصميم المترجمات، معالجة النصوص، وتصميم الخوارزميات، وتوفر تمارين تطبيقية لتعزيز الفهم.