تالار گفتمان مانشت

سلام میشه برام خیلی ساده توضیح بدین گرامر مستقل از متن چیه؟
راستش من هرچقدر کتاب رو خوندم اخرش نفهمیدم گرامر مستقل از متن چیه؟
چرا بهش میگن مستقل از متن؟
همچنین گرامر منظم هم همینطور ممنون میشم توضیح بدین

واسه گرامر منظم اول مهمه گرامر خطی رو بدونید بعضی از تعاریف رو کتاب لینز هستش )
تعریف گرامر خطی: گرامر خطی گرامری است که در آن حداکثر یک متغیر (همون حروف بزرگ مثل S) می تواند در سمت راست یک
قانون یافت شود بدون این که محدودیتی در محل این متغیر وجود داشته باشد.

به گرامری که متغیر سمت راست آن آخرین حرف باشد گرامر خطی راست می گویند یعنی تمام قواعد به شکل زیر باشد :



و به گرامری که متغیر اولین حرف آن باشد گرامر خطی چپ می گویند. یعنی همه قواعد به صورت :


که [tex]A ,B\in V[/tex] و [tex]x\in T^{*}[/tex] هستند .


مثال :

[tex]S\rightarrow abS|a[/tex] گرامر خطی راست و [tex]S\rightarrow Sab|ab[/tex] گرامر خطی چپ است

هر گرامری که خطی چپ یا خطی راست باشد گرامر منظم می باشد .


اما گرامر زیر با اینکه خطی هست(چون سمت راست قانون فقط یک متغیر که S است قرار دارد) اما چون خطی راست و چپ نیست پس منظم نیست .
[tex]S\rightarrow aSb|ab[/tex]

---

در مورد گرامر مستقل از متن ما کلا دو سمت داریم [tex]S\rightarrow a[/tex] ، اگر دقت کنید S در سمت چپ و a در سمت راست قرار دارد در مورد مستقل از متن ما محدودیتمان در سمت چپ است که ما این اجازه را داریم که فقط یک متغیر(مثل S) در سمت چپ داشته باشیم اما در سمت راست در گرامر منظم همان طور گفتیم باید فقط یک متغیر باشد که یا در منتهی الیه سمت راست یا چپ است اما در گرامر مستقل هیچ محدودیتی نداریم یعنی هر تعداد متغیر و حرف میتواند در سمت راست داشته باشیم بدون محدودیت مکان .یعنی به فرم زیر باشد : [tex]A\rightarrow x[/tex] که [tex]A \in V[/tex] و [tex]x\in (V\bigcup T)^{*}[/tex]

گرامرهای مستقل از متن نام خود را از این واقعیت می گیرند که میتوان متغیر سمت چپ هر قانون را در هر زمانی که متغیردر یک شکل جمله ای ظاهر شود جایگزین نمود . این کار به نماد ها در بقیه شکل جمله ای(یا همان متن ) بستگی ندارد

خیلی ممنون شفاف و عالی بود
چی میشد بجای چند صفحه توضیح بیخود مثلا شما چند خط مفیدمینوشت
همیشه برام سواله چرا به این شیوایی که استاد و دوستان توضیخ میدن همینجوری توی کتاب نمینویسند؟ یه جور مینویسند که آدم 10 بار بخونه آخرشم شک داشته باشه فهمیده یا نه

شاید مرور این نکته هم بد نباشه که :
گرامر منظم : محدود ، مبهم نیست ، برای آن dfa یا nfa میتوان رسم نمود

سلام

میشه جمله زیر رو با یک مثال توضیح بدید؟

نقل قول: گرامرهای مستقل از متن نام خود را از این واقعیت می گیرند که میتوان متغیر سمت چپ هر قانون را در هر زمانی که متغیردر یک شکل جمله ای ظاهر شود جایگزین نمود . این کار به نماد ها در بقیه شکل جمله ای(یا همان متن ) بستگی ندارد