سلام من تازه عضو شدم و امیدوارم در کنار همه اعضای اینجا چیزای جدیدی یاد بگیرم
چند تا سوال داشتم:
1. اصولا فرق بین گرامرای مستقل از متن با گرامرهای معمولی چیه؟ اگه برای یه زبان هر گرامری بنویسیم اون زبان مستقل از متنه ؟ و اون گرامر، گرامر مستقل از متن حساب میشه؟
2. فرض کنیم یه گرامر این شکلی باشه:
s>M|N
M>AD
A>aAb|landa
D>bDc|landa
N>aNc|A
میدونیم ک مستقل از متنه، اما از کجا ؟ نشانه اون چیه ؟ ضمن اینکه ترتیب اجراش چطوری؟
باید همه جایگزاری‌ها انجام بشه ب ترتیب؟ چطوریه ؟
یعنی s یکبار باید m بشه و دقیقا بعد از اون n بشه ؟ ....
راهنمایی لطفا
یکی از شرایطش اینه که سمت چپ فقط و فقط یک متغیر باشه.( یعنی یک متغیر باشه و هیچ ترمینالی هم نباشه)
نوع دیگری از گرامرها حساس به متن هستند.
که گرامرهای مستقل از متن زیر مجموعه گرامرهای حساس به متن هستند.
اگر کتاب پیترلینز رو دارید قسمت زبان مستقل از متن و گرامر مستقل از متن رو بخونید من الان کتاب ندارم که از روی کتاب واستون بگم.
مرسی از پاسختون
سول یک چندین سوال کوتاه بود ممنون میشم پاسخ بدید
ضمن اینکه نحوه تولید اون گرامر به ه ترتیبی است؟
هر زبانی که بشه واسش یه گرامر مستقل از متن نوشت مستقل از متنه.
هر جایگذاری یه رشته رو به ما میده که اون رشته عضو زبانه.
میتونه یه سری از قواعد بلا استفاده باشه که بهش میگن قواعد بی فایده یعنی میشه حذفشون کرد.
ترتیب اصلا مهم نیست فقط اولین قانونی که استفاده میشه اونی هست که سمت چپش متغیر شروع یا S قرار داره.
مثلا گرامر
[tex]S\rightarrow aSb | ab[/tex]
زبان
[tex]a^nb^n|n>=1[/tex]
را تولید میکنه.
شما میتونید با استفاده از قواعد فوق رشته های ab ,aabb,..... رو تولید کنید.
حالا اگر خودتون بخواهید برای این زبان گرامر بنویسید باید بدانید که با اضافه کردن هر a یک b نیز باید اضافه شود و به نحوه ای اضافه شود که تمام aها قبل از bها بیاید. با بررسی چند گرامر خاص و اندکی تمرین میتونید برای هر زبان مستقل از متن گرامر بنویسید.
[tex]S\rightarrow aAbB|aSb|ab[/tex]
[tex]C\rightarrow ba[/tex]
[tex]A\rightarrow aa|a[/tex]
[tex]B\rightarrow bb[/tex]
خوب توی این گرامر C یک قاعده بی فایده است چون اصلا از S نمیشه به C رسید.
پس میشه حذفش کرد.
حالا با شروع از S و طی یک مسیر دلخواه یک رشته تولید میکنیم .
[tex]S\rightarrow aAbB[/tex]
[tex]A\rightarrow a[/tex]
[tex]B\rightarrow bb[/tex]
این مسیر منجر به تولید رشته aabbb میشه.
بازم اگه سوالی بود بپرسید.
به عنوان تمرین میتونید گرامر زبانهای به صورت
[tex]WW^{R} | W \epsilon (a,b)^{*}[/tex]
[tex]a^{2n}b^{2n}[/tex] رو بنویسید.
مرسی آفاق جون
1.اینکه سمت چپش فقط‌ی متغیر باشه اون متغیر همونیه ک با فلش اشاره میده به عبارت دیگه ؟
2.مثلا تو گرامر دومی ک فرمودید S,A,B,C اون متغیر هایی هستند ک باید تنها باشند ؟
3.در همون گرامر، S، عبارت aSb متغیر حساب نمیشه ؟
4. ترمینالها کدام هستند
بله مثلا S به تنهایی اومده اگر تنها نباشه و مثلا SB باشه احتمالا گرامر حساس به متنه.
ترمینالها همون حروف کوچک هستند که جزوی از الفبا هستند مثلا a,b,....