سلام دوستان خسته نباشید!!
سوال داشتم در مورد پیدا کردن Head یک زبان از روی گرامر مستقل از متنش!!
کسی الگوریتمی داره؟
اگر منظورتون از head : [tex]head(L)=\{x:\: y\: \in Sigma^{\ast}\: for\: xy\in L\}[/tex] باشد :
گرامر مستقل از متن که دارید رو طی مراحلی به فرم گریباخ ببرید - سپس با طی n مرحله رشته های موجود رو یاداشت کنید-x رو دارید!
ببخشید مگه چندتا head درایم تو نظریه!!!
ممنون بایت جوابتون اما من میخوام با عملگر head از روی گرامر یک زبان مثل L گرامر Head اون زبان رو بدست بیارم!!!
این تمرین ۱۲ بخش ۱-۵ لینزه
روند کار رو از روی مثال توضیح می دم:
فرض کنید گرامر ما به این صورت باشه:
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