واسه گرامر منظم اول مهمه گرامر خطی رو بدونید

بعضی از تعاریف رو کتاب لینز هستش )
تعریف گرامر خطی: گرامر خطی گرامری است که در آن حداکثر یک متغیر (همون حروف بزرگ مثل S) می تواند در سمت راست یک
قانون یافت شود بدون این که محدودیتی در محل این متغیر وجود داشته باشد.
به گرامری که متغیر سمت راست آن آخرین حرف باشد گرامر خطی راست می گویند یعنی تمام قواعد به شکل زیر باشد :
A→xB
A→x
و به گرامری که متغیر اولین حرف آن باشد گرامر خطی چپ می گویند. یعنی همه قواعد به صورت :
A→Bx
A→x
که
A,B∈V و
x∈T∗ هستند .
مثال :
S→abS|a گرامر خطی راست و
S→Sab|ab گرامر خطی چپ است
هر گرامری که خطی چپ یا خطی راست باشد گرامر منظم می باشد .
اما گرامر زیر با اینکه خطی هست(چون سمت راست قانون فقط یک متغیر که S است قرار دارد) اما چون خطی راست و چپ نیست پس منظم نیست .
S→aSb|ab
در مورد گرامر مستقل از متن ما کلا دو سمت داریم
S→a ، اگر دقت کنید S در سمت چپ و a در سمت راست قرار دارد در مورد مستقل از متن ما محدودیتمان در سمت چپ است که ما این اجازه را داریم که فقط یک متغیر(مثل S) در سمت چپ داشته باشیم اما در سمت راست در گرامر منظم همان طور گفتیم باید فقط یک متغیر باشد که یا در منتهی الیه سمت راست یا چپ است اما در گرامر مستقل هیچ محدودیتی نداریم یعنی هر تعداد متغیر و حرف میتواند در سمت راست داشته باشیم بدون محدودیت مکان .یعنی به فرم زیر باشد :
A→x که
A∈V و
x∈(V⋃T)∗
گرامرهای مستقل از متن نام خود را از این واقعیت می گیرند که میتوان متغیر سمت چپ هر قانون را در هر زمانی که متغیردر یک شکل جمله ای ظاهر شود جایگزین نمود . این کار به نماد ها در بقیه شکل جمله ای(یا همان متن ) بستگی ندارد