دورة : Automates à pile – نظرية اللغات

يتناول هذا المستند مفهوم automates à pile (آلات المكدس) كجزء أساسي من نظرية اللغات والحسابات. يبدأ بتعريف المكونات الأساسية: الحالة الحالية، الرمز المدخل، رمز المكدس الفارغ، ومجموعة الحالات، أبجدية الدخول، أبجدية المكدس، دالة الانتقال، الحالة الأولية، ومجموعة الحالات النهائية. ثم يشرح الحركات deterministe للآلة عند قراءة رمز من الشريط ومطابقة قمة المكدس، موضحاً كيف تقوم الآلة بالتحرك إلى اليمين، إجراء عمليات على المكدس (إدخال أو إخراج رموز)، وتغيير الحالة. بعد ذلك يقدم التعريف الرسمي للautomate على شكل السداسي (Q, Σ, Γ, δ, q₀, Z₀, F) ويوضح صيغة دالة الانتقال δ: Q × Σ × Γ → Q × Γ* مع تفسير نتائجها بناءً على طول السلسلة المخرجّة من المكدس (إفراغ، بقاء، أو إدخال رموز). يتبع ذلك أمثلة توضيحية لبناء automate يقبل اللغة L = {aⁿbⁿ | n≥0} عبر خطوات الانتقال المناسبة. يوضح القسم الثاني تكوين automate كرباعية (الحالة الحالية،remaining input, stack content) ويظهر كيف تتطور التكوينات أثناء معالجة السلسلة، مع مثال على السلسلة aabb. بعد ذلك يناقش اللغات المقبولة بواسطة automate، مميزاً بين القبول بالحالة الفارغة والقبول بالحالة النهائية، ويظهر تكافؤ النوعين عبر إفراغ المكدس. أخيراً يعرض القسم الرابع automates غير deterministe، موضحاً إمكانية وجود عدة انتقالات لنفس الرمز والانتقال الفارغ، مع مثال على اللغة L = {ww | w∈{0,1}⁺}. يختتم المستند بملخص يربط المفاهيم النظرية بالتطبيقات العملية في تحليل المترجمات وتصميم اللغات الشكلية.