CNF يرمز إلى الشكل الطبيعي لتشومسكي. يكون CFG (القواعد النحوية الخالية من السياق) في CNF (صيغة تشومسكي العادية) إذا كانت جميع قواعد الإنتاج تستوفي أحد الشروط التالية:
- ابدأ في توليد الرمز ε، على سبيل المثال، A → ε.
- محطة غير طرفية تولد محطتين غير طرفيتين. على سبيل المثال، S → AB.
- محطة غير طرفية تولد محطة. على سبيل المثال، S → أ.
على سبيل المثال:
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} تتوافق قواعد الإنتاج الخاصة بـ Grammar G1 مع القواعد المحددة لـ CNF، لذا فإن القواعد النحوية G1 موجودة في CNF. ومع ذلك، فإن قاعدة إنتاج القواعد G2 لا تفي بالقواعد المحددة لـ CNF حيث أن S → aZ يحتوي على محطة متبوعة بغير طرفية. لذا فإن القواعد النحوية G2 ليست في CNF.
عجلة التمرير لا تعمل
خطوات تحويل CFG إلى CNF
الخطوة 1: قم بإزالة رمز البداية من RHS. إذا كان رمز البداية T على الجانب الأيمن من أي إنتاج، فقم بإنشاء إنتاج جديد على النحو التالي:
S1 → S
حيث S1 هو رمز البداية الجديدة.
الخطوة 2: في القواعد، قم بإزالة المنتجات الفارغة والوحدة وغير المفيدة. يمكنك الرجوع إلى تبسيط CFG .
إزالة الحرف الأخير من السلسلة
الخطوه 3: قم بإزالة المحطات الطرفية من RHS للإنتاج إذا كانت موجودة مع محطات طرفية أو غير طرفية أخرى. على سبيل المثال، يمكن تحليل الإنتاج S → aA على النحو التالي:
S → RA R → a
الخطوة 4: قم بإزالة RHS مع أكثر من طرفين غير طرفيين. على سبيل المثال، يمكن تحليل S → ASB على النحو التالي:
S → RS R → AS
مثال:
تحويل CFG معين إلى CNF. خذ بعين الاعتبار القواعد النحوية G1:
S → a | aA | B A → aBB | ε B → Aa | b
حل:
الخطوة 1: سنقوم بإنشاء إنتاج جديد S1 → S، حيث يظهر رمز البداية S على RHS. القواعد النحوية ستكون:
S1 → S S → a | aA | B A → aBB | ε B → Aa | b
الخطوة 2: نظرًا لأن القواعد النحوية G1 تحتوي على إنتاج A → ε null، فإن إزالتها من القواعد النحوية تؤدي إلى:
البث
S1 → S S → a | aA | B A → aBB B → Aa | b | a
الآن، نظرًا لأن القواعد النحوية G1 تحتوي على وحدة الإنتاج S → B، فإن ناتج الإزالة الخاص بها:
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a
قم أيضًا بإزالة وحدة الإنتاج S1 → S، وإزالتها من عوائد القواعد:
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a
الخطوه 3: في قاعدة الإنتاج S0 → aA | أأ، ق → أأ | Aa، A → aBB وB → Aa، الطرفية a موجودة على RHS مع غير أطرافها. لذلك سوف نستبدل المحطة a بـ X:
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a
الخطوة 4: في قاعدة الإنتاج A → XBB، يحتوي RHS على أكثر من رمزين، مما يؤدي إلى إزالته من العائد النحوي:
تخطي القائمة
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB
ومن ثم، بالنسبة للقواعد المحددة، هذا هو CNF المطلوب.