Simplifying CFGs (تبسيط القواعد)
قبل تحويل القواعد أو التعامل معها، يجب تنظيفها من "الشوائب". الترتيب مهم جداً:
1. Eliminate $\epsilon$
تخلص من قواعد $A \to \epsilon$.
(إلا إذا كانت S تنتج $\epsilon$).
2. Eliminate Unit
تخلص من قواعد $A \to B$.
(استبدلها بإنتاجات B مباشرة).
3. Eliminate Useless
احذف الرموز التي لا تنتج كلمات (Non-generating) أو لا يمكن الوصول إليها (Unreachable).
Chomsky Normal Form (CNF)
في CNF، كل قاعدة يجب أن تكون بأحد شكلين فقط:
متغيرين (Variables)
رمز نهائي واحد (Terminal)
- يجعل شجرة الإعراب (Parse Tree) ثنائية (Binary Tree).
- يسمح باستخدام خوارزمية CYK للتحقق من انتمائية الكلمة في وقت $O(n^3)$.
- طول الاشتقاق لأي كلمة طولها $w$ هو بالضبط $2|w| - 1$ خطوة.
Pumping Lemma for CFLs
The "uvwxy" Theorem
لأي لغة CFL، يوجد طول ضخ $n$. أي كلمة $z$ طولها $\ge n$ يمكن تقسيمها إلى 5 أجزاء: $z = uvwxy$ بحيث:
- $|vx| \ge 1$ (على الأقل واحد منهما غير فارغ).
- $|vwx| \le n$ (الضخ يحدث في نطاق محدود).
For all $i \ge 0$, $uv^iwx^iy \in L$
نضخ الجزئين $v$ و $x$ معاً وبنفس التكرار.
تستخدم هذه النظرية لإثبات أن لغة مثل $L = \{a^n b^n c^n\}$ ليست CFL (لأننا نضخ في مكانين فقط، والثالث سيختل توازنه).
Closure & Decision Properties
Closure Properties (الانغلاق)
Decision Properties (القرارات)
- Emptiness: هل $L(G) = \emptyset$؟ (نعم، يمكن فحصه بالتحقق من الوصول للرموز النهائية).
- Finiteness: هل اللغة نهائية؟ (نعم، بالبحث عن Cycles في الـ Dependency Graph).
- Membership: هل $w \in L$؟ (نعم، باستخدام خوارزمية CYK).
- Ambiguity: هل القواعد غامضة؟ (غير قابل للحل Undecidable!).
Intersection of 2 CFLs
هل تقاطع لغتين CFL هو CFL؟
لا!
مثال: $L_1 = \{a^n b^n c^m\}$ (CFL) تقاطع $L_2 = \{a^m b^n c^n\}$ (CFL) ينتج $\{a^n b^n c^n\}$ وهي ليست CFL.
CYK Algorithm
تستخدم لفحص هل الكلمة تنتمي للغة أم لا (Membership).
تعمل فقط مع القواعد بصيغة CNF.
التعقيد الزمني: $O(n^3)$ حيث $n$ طول الكلمة.