Support de cours: نظرية اللغات – علوم الحاسوب – Théorie des langages

يقدم هذا المستند دعمًا coursًا شاملاً لمادة نظرية اللغات المخصصة لطلاب السنة الثانية ليسانس في تخصص علم الحاسوب بجامعة فرحات عباس سطيف 1. يبدأ المقدمة بتعريف المفاهيم الأساسية مثل الرموز والكلمات واللغات كمجموعات من الكلمات على أبجدية، ثم يوضح العمليات المعرفة على اللغات مثل الاتحاد والتقاطع والتكميل والاختلاف والconcaténation وإغلاق كلييني، مع أمثلة توضيحية وتمارين لتطبيق lemme de Lévi. بعد ذلك، يتناول الفصل الثاني الجرامر كرباعيات (الرموز النهائية، غير النهائية، الرمز الابتدائي، قواعد الإنتاج) ويشرح مفهوم الاستنتاج والاشتقاق في خطوة واحدة ومتعددة الخطوات، ويعرض مثالًا على جرامر للتعبيرات الحسابية. يلي ذلك عرض هرم تشومسكي للجرامر من النوع 0 إلى النوع 3، مع ربط كل نوع بنوع اللغة المقابلة والآلة التي تتعرف عليها (آلات الحالة المحددة للغة المنتظمة، آلات المكدسة للغة السياقية الحرة، وآلة تورينغ للغة السياقية والحسابية). يخصص الفصل الثالث للغة المنتظمة والتعبيرات العادية، موضحًا تعريفها، واستخدامها في وصف الأنماط، وتحويل الجرامر الخطية إلى اليمين أو اليسار إلى آلات حالة محدودة والعكس، مع خوارزميات التحويل المتبادل. يركز الفصل الرابع على الجرامر السياقية الحرة واللغات الجبرية، موضحًا تعريف الاشتقاق وأشجار الاشتقاق، ومفهوم الغموض، وتبسيط الجرامر وتحويلها إلى الشكل الطبيعي لتشومسكي وغريباخ. يتناول الفصل الخامس آلات المكدسة، تعريفها الرسمي، تمثيلها البياني، مثال المتتاليات المتقابلة (palindromes)، وشروط القبول بالحالة النهائية أو بالمكدس الفارغ. أخيرًا، يدرس الفصل السادس آلة تورينغ، تعريفها كسباعي، علاقات الانتقال، التكوين، اللغات التي تتعرف عليها (اللغة القابلة للحساب واللغة القابلة للعدّ بشكل متكرر)، والوظائف التي تحسبها، مع مناقشة آلة تورينغ المكافئة والعالمية. يرفق المستند بتمارين TD في نهاية كل قسم لتطبيق المفاهيم النظرية على حلول عملية، مما يعزز الفهم ويعد الطلاب للامتحانات والتطبيقات اللاحقة في مجالات مثل المترجمات ومعالجة اللغات الطبيعية.