GNF لتقف على الشكل الطبيعي لـ Greibach. يكون CFG (القواعد النحوية الخالية من السياق) في GNF (نموذج Greibach العادي) إذا كانت جميع قواعد الإنتاج تستوفي أحد الشروط التالية:
- رمز البدء يولد ε. على سبيل المثال، S → ε.
- غير محطة توليد محطة. على سبيل المثال، أ → أ.
- محطة غير طرفية تولد محطة طرفية يتبعها أي عدد من المحطات غير الطرفية. على سبيل المثال، S → aASB.
على سبيل المثال:
G1 = aB, A → aA G2 = S → aAB
تتوافق قواعد إنتاج القواعد G1 مع القواعد المحددة لـ GNF، لذا فإن القواعد النحوية G1 موجودة في GNF. ومع ذلك، فإن قاعدة الإنتاج الخاصة بـ Grammar G2 لا تفي بالقواعد المحددة لـ GNF مثل A → ε و B → ε تحتوي على ε (رمز البداية فقط يمكنه إنشاء ε). لذا فإن القواعد النحوية G2 ليست في GNF.
واجهة قابلة للمقارنة في جافا
خطوات تحويل CFG إلى GNF
الخطوة 1: تحويل القواعد إلى CNF.
إذا لم تكن القواعد النحوية في CNF، فقم بتحويلها إلى CNF. يمكنك الرجوع إلى الموضوع التالي لتحويل CFG إلى CNF: نموذج تشومسكي العادي
الخطوة 2: إذا كانت القواعد النحوية موجودة، فقم بإزالتها.
إذا كان السياق النحوي الحر يحتوي على التكرار الأيسر، فقم بإزالته. يمكنك الرجوع إلى الموضوع التالي للتخلص من العودية اليسرى: العودية اليسرى
الخطوه 3: في القواعد، قم بتحويل قاعدة الإنتاج المحددة إلى نموذج GNF.
تاريخ التحويل إلى سلسلة
إذا لم تكن أي قاعدة إنتاج في القواعد النحوية في نموذج GNF، فقم بتحويلها.
كيفية الحصول على التاريخ الحالي في جافا
مثال:
S → XB | AA A → a | SA B → b X → a
حل:
نظرًا لأن القواعد النحوية G موجودة بالفعل في CNF ولا يوجد أي تكرار متبقي، لذلك يمكننا تخطي الخطوة 1 والخطوة 2 والانتقال مباشرة إلى الخطوة 3.
قاعدة الإنتاج A → SA غير موجودة في GNF، لذلك نستبدل S → XB | AA في قاعدة الإنتاج A → SA على النحو التالي:
S → XB | AA A → a | XBA | AAA B → b X → a
قاعدة الإنتاج S → XB وB → XBA غير موجودة في GNF، لذلك نستبدل X → a في قاعدة الإنتاج S → XB وB → XBA على النحو التالي:
S → aB | AA A → a | aBA | AAA B → b X → a
الآن سوف نقوم بإزالة العودية اليسرى (A → AAA)، نحصل على:
S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a
الآن سنقوم بإزالة الإنتاج الفارغ C → ε، نحصل على:
ترقيم الأبجدية
S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a
قاعدة الإنتاج S → AA غير موجودة في GNF، لذلك نستبدل A → aC | أباك | أ | aBA في قاعدة الإنتاج S → AA على النحو التالي:
S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a
قاعدة الإنتاج C → AAC ليست في GNF، لذلك نستبدل A → aC | أباك | أ | aBA في قاعدة الإنتاج C → AAC على النحو التالي:
S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a
وبالتالي، هذا هو نموذج GNF للقواعد G.