What is a CFG؟
هي طريقة لوصف اللغات باستخدام قواعد "استبدال" (Substitution Rules).
The 4-Tuple $(V, T, P, S)$:
- V (Variables): رموز غير نهائية (Non-terminals) يمكن استبدالها (عادة حروف كبيرة مثل A, B, S).
- T (Terminals): رموز نهائية تكون الجملة (حروف صغيرة، أرقام، أقواس).
- P (Productions): قواعد الاستبدال. شكلها: $A \to \alpha$.
- S (Start Symbol): المتغير الذي نبدأ منه الاشتقاق.
Derivations & Parse Trees
Example: $L = \{0^n 1^n\}$
لإنتاج الكلمة 0011:
- S $\Rightarrow$ 0S1
- $\Rightarrow$ 0(0S1)1 = 00S11
- $\Rightarrow$ 00($\epsilon$)11 = 0011
Types of Derivation
-
Leftmost Derivation:
نستبدل دائماً المتغير الموجود في أقصى اليسار أولاً. -
Rightmost Derivation:
نستبدل دائماً المتغير الموجود في أقصى اليمين أولاً.
Parse Tree (شجرة الإعراب)
تمثيل رسومي لعملية الاشتقاق. (الجذر S، الأوراق Terminals).
Yield: 0011
Ambiguity (الغموض)
متى تكون القواعد غامضة؟
إذا كان لنفس الكلمة (String) أكثر من شجرة إعراب (Parse Tree) مختلفة (أو أكثر من Leftmost Derivation).
الكلمة id + id * id يمكن فهمها بطريقتين:
1. (id + id) * id
2. id + (id * id) ✓ (الصحيح رياضياً)
الحل (Disambiguation):
- فرض أسبقية العمليات (Precedence): الضرب أقوى من الجمع.
- فرض الترابط (Associativity): من اليسار لليمين.
- إعادة كتابة القواعد (Rewrite Grammar) لتطبيق هذه القيود.
Inherently Ambiguous Language
هل الغموض في القواعد أم في اللغة؟
أحياناً تكون اللغة نفسها "مريضة" ولا يمكن كتابة أي قواعد (CFG) لها بدون غموض.
مثال: $L = \{a^n b^n c^m\} \cup \{a^n b^m c^m\}$.
Is every Regular Language a CFL؟
نعم! اللغات المنتظمة هي مجموعة جزئية (Subset) من اللغات الخالية من السياق.
كل DFA يمكن تحويله بسهولة إلى CFG.
العكس غير صحيح (ليست كل CFL هي Regular).