Course: Grammaires hors contexte – Théories des langages

يتناول هذا المستند مفهوم الجرammar(formal grammars) كأدوات للتعرف على وتوليد جمل لغة معينة، مع التركيز على الجرammar hors contexte (غير السياقية). يبدأ بتعريف الجرammar كرباعية G = (V, T, P, S) حيث V هو مجموعة الرموز غير النهائية، T الرموز النهائية، P مجموعة قواعد الإنتاج، S الرمز الابتدائي. يشرح المستند كيفية بناء الجمل باستخدام القواعد مثل -> وتقديم أمثلة على التعبيرات الحسابية الصحيحة والخاطئة. ثم ينتقل إلى notion de dérivation (الاشتقاق) وي distinguer بين الاشتقاق الأيسر والاشتقاق الأيمن، مع توضيح كيفية استبدال الرمز غير النهائي الأيسر أو الأيمن في كل خطوة. بعد ذلك يُقدّم مفهوم شجرة الاشتقاق كتمثيل بصري لاستنتاج الجملة من الرمز الابتدائي، وشروط أن تكون شجرة صالحة: العقد الداخلية تحمل رموز غير نهائية، الأوراق تحمل رموز نهائية، وكل فرع يطابق قاعدة إنتاج. يُناقش أيضًا مفهوم الغموض (ambiguïté) حيث تقبل الجملة أكثر من اشتقاق مختلف، موضحًا ذلك بمثالgrammar ينتج كلمة aabb عبر اشتقاقات مختلفة. أخيرا يشرح اللغة المولدة L(G) كالمجموعة من جميع السلاسل النهائية القابلة للاشتقاق من S، ومفهوم تكافؤ الجرammar: جرammarين متكافئين إذا ولدا نفس اللغة، مع مثال يوضح تحويل قواعد الإنتاج للوصول إلى نفس اللغة aⁿbⁿ. يهدف المستند إلى تمكين الطالب من تحليل grammars، بناء أشجار اشتقاق، تحديد ما إذا كانت grammar غامضة، وتحقق تكافؤ جرammarين.