TD 01: Automates d’états finis – نظرية اللغات

هذا المستند هو تمرين موجه (TD) من مادة نظرية اللغات للسنة الثانية ليسانس، ويتضمن تسعة تمارين تركز على دراسة automata ذات الحالات المحدودة (AFD و AFND). يبدأ التمرين الأول بتحليل automata معطى عبر جدول الانتقال لتحديد ما إذا كان محددًا، وقبول كلمات معينة، ولغة المقبولة. التمرين الثاني يتطلب بناء automata محددة للغات تنتهي بـ 01 وتحتوي على 101. التمرين الثالث يطلب بناء automata للتعبيرات المنتظمة المعطاة مثل 0*1*0* و 0*+11* وغيرها. التمرين الرابع يصف اللغات المقابلة لـ automata في الأشكال 1-9 باستخدام تعبيرات منتظمة. التمرين الخامس يحول automata غير المحددة للتعبيرات r3 و r1 إلى automata المحددة المكافئة. التمرين السادس يبني automata للغات مثل الكلمات التي تنتهي بـ 11، والكلمات ذات الطول الفردي، والكلمات التي تبدأ وتنتهي بـ 0، والكلمات التي عدد 1 فيها مضاعف لـ 3، والكلمات التي تحتوي على 010 على الأقل مرة واحدة، مع تحديد ما إذا كان automata محددًا أم لا. التمرين السابع يبني automata التي لا تحتوي علىsubstring 101. التمرين الثامن يعمل على تكملة اللغات وبناء automata للتجميع والكر star. التمرين التاسع يركز على تقليل automata إلى الشكل الأدنى ويظهر أن automata للغة L2 من التمرين الثاني هو بالفعل أدنى. يهدف هذا TD إلى تعزيز فهم الطلاب للمفاهيم الأساسية لنظرية اللغات وتطبيقها على حلblems عملية.