حذف بازگشتی چپ از گرامر مستقل از متن

[sjj]

سلام
برای حذف بازگشتی چپ از قانون زیر:

B->Bb|aمی تونیم این کار رو کنیم:


B->aZ
Z->bZ|لاندا
حالا اگه بخوایم قانون بازگشتی چپ رو از گرامر زیر حذف کنیم چجوری می شه؟:متفکر:

B->BBb|a

[mortezamsp]

خب میشه این :
B->aZaZ
Z->bZ | لاندا

[sjj]

خیلی ممنون از جوابتون، ولی این گرامری که شما دادین فقط دو تا a تولید می کنه و بین اونا رو با b ها پر می کنه.
مثلا اشتقاق زیر رو در گرامر اصلی نظر بگیریم:

B=>BBb=>BBbBb=>aBbBb=>aabBb=>aabab
گرامری که شما دادین نمی تونه رشته ی فوق و در حالت کلی رشته هایی که بیش از دو a دارند رو تولید کنه.

در اون گرامر اصلی، چیزی که بدیهیه اینه که رشته ها حتما با aa شروع خواهند شد و با b تموم می شن، مشکل در اون الگوهاییه که وسط ایجاد می شه.:عصبانی++:

[mortez maya]

حذف بازگشتی شده اون گرامر میشه این :

B->aZ
Z->BbZ|اپسیلون

این هم اشتقاقی که sjj نوشته :


B=>aZ
=> aBbZ
=> aaZbZ
=>aabZ
=>aabBbZ
=>aabaZbZ
=>aababZ
=>aabab