The Pumping Lemma (ضخ الكلمات)
أداة رياضية تستخدم لإثبات أن لغة معينة ليست منتظمة (Not Regular).
النص الرسمي:
لأي لغة منتظمة $L$، يوجد عدد ثابت $n$ (Pumping Length).
أي كلمة $w$ في اللغة طولها $\ge n$ يمكن تقسيمها إلى 3 أجزاء: $w = xyz$ بحيث:
- $|y| > 0$ (الجزء الأوسط ليس فارغاً).
- $|xy| \le n$ (التكرار يحدث في البداية).
- For all $i \ge 0$, $xy^iz \in L$ (يمكننا تكرار y لأي عدد وتبقى الكلمة في اللغة).
- افترض أن اللغة $L$ منتظمة (للوصول لتناقض).
- الخصم يعطيك $n$.
- أنت تختار كلمة ذكية $w$ تعتمد على $n$ (مثل $0^n1^n$).
- الخصم يقسمها إلى $xyz$ حسب الشروط.
- أنت تختار $i$ (عدد مرات التكرار) لتجعل الكلمة الجديدة $xy^iz$ خارج اللغة.
- بما أنك وجدت تناقضاً، فالفرضية خاطئة واللغة ليست منتظمة.
Closure Properties (خصائص الانغلاق)
إذا كان لدينا لغتان منتظمتان $L_1$ و $L_2$، فإن العمليات التالية تنتج لغة منتظمة أيضاً:
DFA Minimization (تبسيط الآلة)
Table Filling Algorithm (خوارزمية الجدول)
الهدف: دمج الحالات المتكافئة (Equivalent States) لتقليل حجم الـ DFA.
- ارسم جدولاً لكل زوج من الحالات $(p, q)$.
- ضع علامة $\times$ للأزواج التي أحدها نهائي والآخر غير نهائي (مميزة فوراً).
- للأزواج المتبقية: إذا كان الانتقال برمز ما يؤدي إلى زوج مميز سابقاً، ميز هذا الزوج أيضاً.
- كرر الخطوة 3 حتى لا يوجد تغيير.
- الأزواج غير المميزة يتم دمجها.
Distinguishable Pairs Table
Misusing Pumping Lemma
الـ Pumping Lemma تستخدم فقط لإثبات أن اللغة ليست منتظمة.
لا يمكنك استخدامها لإثبات أن اللغة منتظمة! (قد تنجح الـ Pumping للغة غير منتظمة أحياناً).
$L = \{0^n 1^n | n \ge 0\}$
هذه أشهر لغة غير منتظمة.
السبب: الـ DFA ذاكرته محدودة ولا يستطيع "العد" للتأكد من أن عدد الأصفار يساوي عدد الآحاد إذا كان العدد كبيراً جداً (أكبر من عدد حالاته).