ترجمة القواعد النحوية العودية اليمنى إلى شكل طبيعي تشومسكي

Question

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

أعتقد أنه يمكنني القيام بذلك باستخدام تسلسل ثابت من القواعد بدلاً من القواعد ، لكنني أريد التأكد من أنني لا أتجه في الاتجاه الخاطئ. من الأسهل شرح مثال:

بالنسبة إلى قواعد اللغة التي تنتج n 'a حيث تكون n أكبر من 0 ومضاعفات من ثلاثة: (لا تقلق ، هذا يختلف تمامًا عن قواعد اللغة الفعلية)

S-> Aaaa
A-> Aaaa
A-> ε

هل ستكون الترجمة الصحيحة:

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

على الرغم من أن قواعد اللغة الخاصة بك مثيرة للاهتمام ، يمكنك إجراء تحويل تشكل تشومسكي الطبيعي كما تفعل مع أي قواعد أخرى (غير متكررة) أخرى. ما عليك سوى اتباع الخوارزمية الموضحة في كتابك ، والذي ربما يتكون من خطوتين: (1) استبدال جميع أحداث المحطات أ حسب القواعد أ -> أ, ، أين أ لا يحدث في مجموعة القواعد ؛ (2) تحويل جميع القواعد أ -> ث, ، أين لين(W)> 2 ، وفقًا لقواعد الطول 2 التي تحتوي على متغيرات جديدة.

من اجلك أ القاعدة ، إذن ، بناء قاعدة لاستخلاص المحطات ، على سبيل المثال ك -> أ, واستبدل جميع حوادث المحطة أ:

A -> AKKK

ثم ضع القواعد في CNF

A    -> AA'
A'   -> KA''
A''  -> KK