این تمرین ۱۲ بخش ۱-۵ لینزه
روند کار رو از روی مثال توضیح می دم:
فرض کنید گرامر ما به این صورت باشه:
S-->aABb
A-->aAb|lambda
B-->xy
خب واضحه که گرامر ها همشون از S اشتقاق می شن
و ما تو Head گرفتن از یه زبانی از آخر رشته های اون زبان حذف می کنیم
به تعداد هیچ کاراکتر به تعداد یک کاراکتر به تعداد دو کاراکتر و ... از آخر رشته های زبان کم می کنمی
حالا اگه بخواهیم از آخر رشت ههای زبان کاراکتری رو حذف کنیم باید از آخر S کم کنسم چون می دونیم همه رشته ها از S اشتقاق می شن و اگه توی قانون S-->aABb همه ی نان ترمینال ها جایگذاری بشن رشته ما بدشتاومده پس آخر رشته می شه آخر S

تو همون قانون اول به aABb نگاه کنید اگه از خود این قانون بخواهیم head بگیریم یه بار می شه خودش یه بار می شه این که اون b آخر رو برداریم پس در مورد b آخر دو تا تصمیم داریم باشه یا نباشه که این دو حالت رو این جوری تو گرامر می ذاریم که به جای اون b آخر یه نان ترمینال جدید تعریف می کنیم که می تونه b یا لامبدا باشع پس گرامر بعدی مون می شه:
S1-->aABC
A-->aAb|lambda
B-->xy
C-->b|lambda


خب اگه تصمیم بگیریم که اون b آخر می مونه که هیچ
اما اگه تصمیم بگیریم b آخر رو برداریم پس انگار که در قانون اول به جای C لامیدا قرار دادیم و قانون C رو از گرامرمون برمی داریم
پس قانون اول می شه این شکلی:
S-->aAB
که حالا آخر شته مون میشه آخر B. حالا باز در مورد B آخر بحث می کنیم که باید به جاش xy بذاریم حالا رو آخرین کاراکترش یعنی y حرف می زنیم دو حالت داره بمونه یا برداشته شه
اگه بخواد بمونه که می شه y اگه بخواد برداشته شه باید به جاش لاندا بذاریم پس گرامر دوممون می شه:

S2-->aAB
A-->aAb|lambda
B-->xD
D-->y|lambda

حالا اگه این y بمونه که هیچ اکه نمونه کاراکتر قبلی ش x دو حالت داره بمونه یا برداشته شه گارمر سوم به این صورته:

S3-->aAB
A-->aAb|lambda
B-->x|lambda

اگه جای B رشته x بشینه که هیچ اگگه جاش لامبدا بشینه قانون اول می شه این شکلی:
S-->aA
که حالا این A جاش aAb یا لاندا می شینه به این که ممکنه جاش لاندا بشینه فعلا کار نداریم
اما اگه جای A رشته aAb بشینه باز سر b آخر دو حالت داریم
گرامر چهارممون می شه:

S4-->aA
A-->aAE|lambda
E-->b|lambda

اگه به جای E حرف b ذو بذاریم که هیچ اما اکه لاندا بذاریم می رسیم به aA که اون A آخرش می تونه جاش aA یا لاندا بشینه (که خود گرامر اینو از قبل داشته ) پس:

S5-->aAB
A-->aA|lambda

و بعد خود A اگه جاش لاندا بشینه

S6-->aAB
A-->a|lambda

و اگه در قانون اول به جای A لاندا بشینه :


S7-->a|lambda

و دیگه بیشتر از این جا نداره که کوچیک بشه
یعنی واضحه که همیشه کوچکترین رشته عضو head رشته لاامبداست

حالا گرامر مربوط به Head(L) برابر است با:
S-->S1|S2|S3|S4|S5|S6|S7