تشومسكي الشكل الطبيعي

أدخل رمز بداية جديدًا S ₀ ، وقاعدة جديدة

S ₀ → S ,

حيث S هو رمز البداية السابق. هذا لا يغير اللغة الناتجة عن القواعد النحوية، ولن يظهر S ₀ على الجانب الأيمن لأي قاعدة.

لإلغاء كل قاعدة

أ → س ₁ ... أ ... س _ن

إذا لم يكن الرمز النهائي a هو الرمز الوحيد على الجانب الأيمن، فقم بإدخال رمز غير نهائي جديد Na لكل رمز نهائي من هذا القبيل، وقاعدة جديدة _.

N _a → a .

غيّر كل قاعدة

أ → س ₁ ... أ ... س _ن

ل

A → X ₁ ... N _a ... X _n .

إذا ظهرت عدة رموز طرفية على الجانب الأيمن، فاستبدل كل منها في آنٍ واحد بالرمز غير الطرفي المرتبط بها. هذا لا يُغيّر اللغة الناتجة عن القواعد النحوية. ^{[ 4 ] : ​​92}

استبدل كل قاعدة

أ → س ₁ س ₂ ... س _ن

مع أكثر من رمزين غير طرفيين X1 _، ...، Xn وفقًا _{للقواعد}

أ → س ₁ أ ₁ ،

A ₁ → X ₂ A ₂ ,

... ،

A _{n -2} → X _{n -1} X _n ,

حيث تمثل A _i رموزًا غير طرفية جديدة. ومرة ​​أخرى، هذا لا يغير اللغة الناتجة عن القواعد النحوية. ^{[ 4 ] : ​​93}

قاعدة إبسيلون هي قاعدة على الشكل التالي:

A → ε,

حيث A ليس S ₀ ، رمز بداية القواعد النحوية.

لإلغاء جميع القواعد من هذا الشكل، حدد أولاً مجموعة جميع الرموز غير الطرفية التي تشتق ε. يطلق هوبكروفت وأولمان (1979) على هذه الرموز غير الطرفية اسم الرموز القابلة للإلغاء ، ويحسبونها على النحو التالي:

• إذا كانت القاعدة A → ε موجودة، فإن A قابلة للإلغاء.
• إذا كانت القاعدة A → X ₁ ... X _n موجودة، وكان كل X _i قابلاً للإلغاء، فإن A قابل للإلغاء أيضًا.

احصل على قواعد نحوية وسيطة عن طريق استبدال كل قاعدة

أ → س ₁ ... س _ن

في جميع الإصدارات مع حذف بعض الرموز القابلة للإلغاء X _i . بحذف كل قاعدة إبسيلون في هذه القواعد، ما لم يكن جانبها الأيسر هو رمز البداية، نحصل على القواعد المُحوَّلة. ^{[ 4 ] : ​​90}

على سبيل المثال، في القواعد النحوية التالية، مع رمز البداية S ₀ ،

S ₀ → AbB | C

ب → أأ | أج

ج → ب | ج

A → a | ε

الرمز غير الطرفي A ، وبالتالي B أيضاً ، قابل للإلغاء، بينما C و S ₀ ليسا كذلك . ومن ثم نحصل على القواعد النحوية الوسيطة التالية: ^{[ ملاحظة 3 ]}

S ₀ → A b B | A b B | A b B | A b B | C  

ب → أأ | أأ | أأ | أ ε أ | أ ج | أ ج​​  

ج → ب | ج

A → a | ε

في هذه القواعد النحوية، تم تضمين جميع قواعد إبسيلون في موقع الاستدعاء. ^{[ ملاحظة 4 ]} في الخطوة التالية، يمكن حذفها، مما ينتج عنه القواعد النحوية التالية:

S ₀ → AbB | Ab | bB | b  | C 

ب → أأ | أ  | أج | ج 

ج → ب | ج

أ → أ

تنتج هذه القواعد نفس لغة المثال النحوي الأصلي، أي. { ab , aba , abaa , abab , abac , abb , abc , b , ba , baa , bab , bac , bb , bc , c } ، ولكن لا يوجد لديه قواعد ε.

قاعدة الوحدة هي قاعدة من الشكل

أ → ب ،

حيث A و B رموز غير طرفية. لإزالتها، لكل قاعدة

ب → س ₁ ... س _ن ،

حيث X1 ... Xn عبارة عن سلسلة من _الرموز غير الطرفية والطرفية، قاعدة _الجمع

أ → س ₁ ... س _ن

إلا إذا كانت هذه قاعدة وحدة تمت إزالتها بالفعل (أو يجري إزالتها). يُمكن تخطي الرمز غير الطرفي B في القواعد النحوية الناتجة لأن B عنصر من عناصر الإغلاق الوحدوي للرمز غير ^الطرفي A. ^{[ 9} ]

الحفاظ المتبادل على نتائج التحويل

يحافظ التحويل X دائمًا على ( Y ) وقد يدمر ( N ) نتيجة Y :
Y X	يبدأ	شرط	صندوق	دل	وحدة
يبدأ
شرط
صندوق
دل
وحدة				( Y ) *
* يحتفظ الأمر UNIT بنتيجة الأمر DEL  إذا تم استدعاء الأمر START من قبل.

عند اختيار ترتيب تطبيق التحويلات المذكورة أعلاه، يجب مراعاة أن بعض التحويلات قد تُبطل نتائج تحويلات أخرى. على سبيل المثال، سيعيد التحويل START تطبيق قاعدة الوحدة إذا طُبِّق بعد التحويل UNIT . يوضح الجدول الترتيبات المسموح بها.

علاوة على ذلك، يعتمد تضخم حجم القواعد النحوية في أسوأ الحالات ^{[ ملاحظة 5 ]} على ترتيب التحويل. باستخدام | G | للدلالة على حجم القواعد النحوية الأصلية G ، قد يتراوح تضخم الحجم في أسوأ الحالات من | G | ^² إلى ^{2/2 |G|} ، وذلك اعتمادًا على خوارزمية التحويل المستخدمة. ^{[ 8 ] : 7} يعتمد تضخم حجم القواعد النحوية على الترتيب بين DEL و BIN . قد يكون التضخم أُسّيًا عند تنفيذ DEL أولًا، ولكنه خطي في غير ذلك. يمكن أن يتسبب UNIT في تضخم تربيعي في حجم القواعد النحوية. ^{[ 8 ] : 5} يؤدي الترتيبان START ، TERM ، BIN ، DEL ، UNIT و START ، BIN ، DEL ، UNIT ، TERM إلى أقل تضخم (أي تربيعي).

طريقة أخرى ^{[ 4 ] : ​​92 [ 10 ]} لتعريف الشكل الطبيعي لتشومسكي هي:

تكون القواعد النحوية الرسمية في شكل تشومسكي المختزل إذا كانت جميع قواعد الإنتاج الخاصة بها على الشكل التالي:

${\displaystyle A\rightarrow \,BC}$أو

${\displaystyle A\rightarrow \,a}$،

أين${\displaystyle A}$،${\displaystyle B}$و${\displaystyle C}$هي رموز غير طرفية، و${\displaystyle a}$هو رمز طرفي . عند استخدام هذا التعريف،${\displaystyle B}$أو${\displaystyle C}$قد يكون رمز البداية. فقط القواعد النحوية الخالية من السياق التي لا تولد سلسلة فارغة يمكن تحويلها إلى شكل تشومسكي المختزل.

في رسالة اقترح فيها مصطلح " صيغة باكوس-ناور " (BNF)، ألمح دونالد إي. كنوث إلى أن "صيغة باكوس-ناور التي تتخذ فيها جميع التعريفات مثل هذه الصيغة يمكن القول إنها في "صيغة فلويد العادية"".

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \mid \langle C\rangle } أو

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \langle C\rangle } أو

${\displaystyle \langle A\rangle$ ::=\,a} ,

أين${\displaystyle \langle A\rangle }$،${\displaystyle \langle B\rangle }$و${\displaystyle \langle C\rangle }$هي رموز غير طرفية، و${\displaystyle a}$يُعدّ رمزًا نهائيًا، لأن روبرت دبليو فلويد وجد في عام 1961 أنه يمكن تحويل أي صيغة BNF إلى الصيغة المذكورة أعلاه. ^{[ 11 ]} لكنه سحب هذا المصطلح، "لأنه لا شك أن العديد من الأشخاص قد استخدموا هذه الحقيقة البسيطة بشكل مستقل في أعمالهم، وهذه النقطة ليست سوى أمر ثانوي بالنسبة للاعتبارات الرئيسية لملاحظة فلويد." ^{[ 12 ]} في حين أن ملاحظة فلويد تستشهد بمقال تشومسكي الأصلي لعام 1959، فإن رسالة كنوت لا تفعل ذلك.