به دست آوردن زبان از روی گرامر و انواع گرامر ها

1396/5/2 محمدرضا احمدآبادی 8679

سلام دوستان عزیزم ، محمدرضا احمدآبادی هستم با جلسه هشتم آموزش نظریه زبان ها درخدمتتون هستم . امیدوارم تا این جا از تعطیلات استفاده کافی و عالی  برده باشید و خستگی را از تنتون به در کرده باشید . امروز میخواهم براتون نحوه بدست آوردن زبان از روی گرامر را بگم و بعد اون هم قصد دارم انواع گرامر هارو براتون بگم .
زبان یک گرامر :
زبان یک گرامر مجموعه تمامی رشته هایی است که توسط آن گرامر پذیرفته میشود .
قانون بازگشتی: هر قاعده به فرم  A→αAβ   که در آن   α,β ԑ (V ᴜ T )  ̽ در یک گرامر ، یک قاعده بازگشتی میباشد.
به زبان خودمونی اگه بخوام جمله بالا را براتون توضیح بدم این طوری میگم که اگه در یک قاعده  یک متغیر که در سمت چپ قاعده قرار دارد در سمت راست خودش دوباره فراخوانی کند  این قاعده را بازگشتی می نامند.
شاید بپرسید قاعده بازگشتی به چه دردی میخورد؟
جواب : قواعد بازگشتی باعث میشوند که زبان یک گرامر نامحدود باشد.
مثال) با توجه به گرامر روبرو

S →AB    
A →aA|a
B→bB|λ


الف) نشان دهید  رشته    w=aaabb  توسط این گرامر پذیرفته میشود.  ب) زبان این گرامر را بدست آورید.
برای اینکه بتونیم جواب قسمت الف را بدست بیاریم دو راه داریم . اول اینکه از راه اشتقاق حل کنیم و به صورت سطری بریم جلو راه دوم  از طریق درخت اشتقاق بریم جلو  .  خب من براتون از هردوراه حل میکنم فقط یادتون باشه در این موارد انتخاب هاتون باید هدفدار باشه.
 جلسه گذشته گفته بودم برای اشتقاق از متغیر شروع استفاده میکنیم و راه را ادامه میدیم.

S →AB


من اگه بیام به جای متغییر A فقط سمبل a را جایگذاری کنم دیگه نخواهم توانست دوتا سمبل بعدیa را تولید کنم. پس مجبورم  از قاعده اول استفاده کنم.

S →AB →aAB


حالا باز به جای متغیرA من میام ازهمون قانون قبلی که استفاده کرده بودم استفاده میکنم. تا بتونم دومین سمبل a را تولید کنم و هم بتونم راهی برای تولید سمبل سوم a هم داشته باشم .

S →AB →aAB →aaAB


در این مرحله من  تا الان دو تا از سمبل های a که در رشته w خواسته بود را تونستم بسازم. حالا میخوام سومین سمبل را بسازم اگه از قاعده اول دوباره استفاده کنم a سوم تولید خواهد شد اما دوباره متغیر A تولید خواهد شد و این تولید متغیر اگه به قوانین این متغیر نگاه کنید میبینید که در هیچ کدام از دو قانونش نمیتونیم λ را تولید کنیم و در هر دو قاعده  حتما یه سمبل a باید تولید بشه . خب حالا من اگه بخوام از قانون اول استفاده کنم خود به خود دارم سمبل چهارم a را هم تولید میکنم که این خلاف رشته خواسته شده هست.  پس باید در این مرحله از قانون دوم استفاده کنم تا هم سومین سمبل را تولید کنم و هم کارم با متغیر A تموم بشه . پس تا به این جا خواهیم داشت:

S →AB →aAB →aaAB →aaaB


حالا نوبت رسید به جایگذاری متغیر B . برای جایگذاری این متغیر دو قانون داریم. اگر از قانون دوم آن استفاده کنم وλ را جایگذاری کنم رشته تولیدی من aaa خواهد شد اما این رشته مورد نظر من نیست پس مجبورم از قاعده اول آن استفاده کنم و سمبل را تولید کنم. پس خواهیم داشت :

S →AB →aAB →aaAB →aaaB →aaabB


همین جایگذاری را یک بار دیگه انجام میدم تا دومین سمبل b راهم تولید کنم.

S →AB →aAB →aaAB →aaaB →aaabB →aaabbB


کار هنوز تموم نشده . چون من در رشته ام هنوز متغیر دارم واین خلاف شرط جلسه گذشته ما هست. برای این که از شر این متغیر B خلاص بشم باید یکی از قوانین متعلق به این سمبل را جایگذاری کنم خب اگر قاعده اول را انتخاب کنم دوباره سمبل b تولید کرده خواهم بود واین دررشته درخواستی سوال نیست . تنها قانون دوم برام باقی مانده پس به جای متغیر B سمبل λ را جایگذاری میکنم پس خواهم داشت:

S →AB →aAB →aaAB →aaaB →aaabB →aaabbB → aaabb


واما روش دوم: خب داستان روش دوم مثل روش اول هست فقط شکل به دست اوردنش  طوری هست که در ذهن بیشتر و بهتر جا میگیره . دیگه حرفای روش اول را تکرار نمیکنم و جواب نهایی که درخت اشتقاق هست را براتون میگذارم .

آموزش نظریه زبان ها و ماشین ها


 قسمت ب سوال از ما زبان این گرامر را میخواهد. دوستان گرامی من برای این که گیج نشوید روند به دست اوردن زبان گرامر را در یک عکس براتون میارم اما برای اینکه بفهمید در این  عکس  چه کاری صورت گرفته به توضیحات بعد از عکسم خوب گوش کنید .  

آموزش نظریه زبان ها و ماشین ها


برای به دست اوردن زبان گرامر یه کاری شبیه به عمل اشتقاق روی گرامر انجام میدهیم اما این بار هدفمون تولید یه رشته خاص نیست بلکه  اینبار هدفمون این هست که الگوی تولید رشته های توسط این گرامر را بدست بیاریم تا با اون الگو بتونیم زبان این گرامر را بنویسیم.
برای این کار متغیر شروع ، شروع میکنیم و متغیر A را بسط میدهیم البته به شکل درست یعنی کل جمله را بسط میدهیم اما تمرکزمون روی این متغیر خواهد بود یه چندباری این کارو انجام که بدیم متوجه میشویم که به همون تعداد که متغیر A را داریم تکرار میکنیم سمبل a هم تکرار میشه و در نهایت مجبوریم برای این که از این متغیر رها بشیم باید یه دونه سمبل a را دیگه از قانون دوم آن بنویسیم و حالا بریم سراغ متغیر B . خب اگه ما این عمل بسط دادنو n بار انجام داده باشیم میتونیم بگیم تا موقعی که متغیر داشتیم n تا سمبل a داشتیم اما در اخرین مرحله  یه سمبل دیگه به رشته ما اضافه خواهد شد تا از متغیر A خلاص بشیم. تا الان دلیل تکرار سمبل a به تعداد n+1 را براتون گفتم  . برای متغیر B هم همین داستانو برای خودتون بگید اما اینبار تفاوت در این خواهد بود که تا زمانی که ما متغیر B داشته باشیم سمبل b را هم خواهیم داشت همون طور که میدونید تعداد b به تعداد a اصلا وابسته نیست . خب ما اگه عمل بسط متغیرB را m بار انجام داده باشیم میتونیم بگیم به تعداد m هم سمبل b خواهیم داشت . اما برای خلاصی از B دیگه احتیاجی به نوشتن سمبل اضافه نیست چون قانون دوم متغیر B اجازه استفاده λ را به ما داده . الان ایده گرامر این هست که یه سری سمبل a باید تولید بشه که حداقل این تعداد a یک خواهد بود ( چون برفرض مثال خواننده اصلا قصد کرد که از همون اول ازشر A خلاص بشه برای همین فوری از قانون دوم سمبل a را جایگزین کرده و سراغ متغیر B میرود.) و یه سری هم سمبل b خواهیم داشت که مقدار حداقل این سمبل میتواند صفر باشد چرا؟
پس زبان این گرامر خواهد بود:

L={a(n+1) b(m) / n,m>=0}


مثال) زبان گرامر زیر را بدست اورید.
 

S → aSa |A
A → bbA|b

آموزش  نظریه زبان ها و ماشین ها

این بار هم همون روند مثال قبلی را برای این گرامر پیاده سازی میکنیم. من برای  شروع چندین بار از قانون اول متغیر شروع استفاده میکنم( بسط میدهم) تا ببینم روند تولید رشته در این قسمت چگونه خواهد بود. خب همون که در شکل میبینید اگر من این قانون را n  بار استفاده کنم n تا سمبلa قبل از متغیر S تولید کرده خواهم بود و n تا سمبل a بعد از متغیر S تولید کرده خواهم بود. پس این طوری بگم به همون تعداد a که قبل از S تولید کرده باشم به همون تعداد هم بعد از S سمبل a خواهم داشت. خب حالا برای ادامه کار این بار به سراغ قانون دوم S میروم  وتوسط این قانون متغیر A میرسم. خب اگر من m  بار از قانون اول متغیر A استفاده کنم  به ازای هر بار دوتا سمبلb تولید کرده خواهم بود. حالا چون من m بار از این قانون استفاده کرده ام پس تعداد b من به ازای این تعداد 2m خواهد بود. حالا من اگه بخوام از شر متغیر A خلاص بشم  مجبورم به قانون دوم این متغیر پناه ببرم و این قانون یک سمبل b در کنار سمبل های b تولید شده قبلی تولید خواهد کرد. پس تعداد b های رشته های مورد پذیرش این گرامر 2m+1 خواهد بود.
تا این جا من مقدار ماکسیمم این دو سمبل را براتون گفتم . حالا برای نوشتن زبان همون طور که میدونید احتیاج به یه قوانین حداقلی داریم. برای اینکار خودتون را جای خواننده بزارید (البته از نوع کم حوصله و راحت طلب)  . این خواننده از متغیر شروع که بخواهد رشته تولید کند مستقیم بدون انتخاب قانون اول( یعنی بدون تولید سمبل a)  میرود سراغ قانون دوم و از اون جا هم وقتی سر وقت متغیر A رسید  فقط از یکبار قانون دوم را استفاده کرده و تمام. یعنی برای تولید رشته توسط این گرامر ما میتونیم اصلا سمبل a نداشته باشیم وفقط یک سمبل b داشته باشیم. پس زبان این گرامر خواهد بود:

L={ a(n) b(2m+1) a(n) / m,n>=0 }


انواع گرامر:
گرامر ها بر طبق دسته بندی مرحوم چامسکی  در چهار گروه طبقه بندی میشوند که عبارتند از :
1)    گرامر های منظم یا باقاعده:
یک گرامر منظم یا باقاعده خواهد بود اگروتنها اگر  خطی از راست یا خطی از چپ باشد.
گرامرهای خطی از راست:  یک گرامر خطی از راست خواهد بود اگر و تنها اگر هر قاعده آن  به یکی از دو شکل زیر باشد .

A →αB   A,B ԑV
A →α    αԑT  ̽


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

گرامر های خطی از چپ:  یک گرامر خطی از چپ خواهد بود اگرو تنها اگر هر قاعده آن  به یکی از دوشکل زیر باشد

A →Bα   A,B ԑ V
A →α  αԑT  ̽


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

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

2)    گرامر های مستقل از متن :
یک گرامر مستقل از متن خواهد بود ، اگر و تنها اگر هر قاعده آن به شکل زیر باشد.

A →α    A ԑ V , α ԑ(V ᴜ T )  ̽


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

نظریه زبان ها و ماشین ها


 هر زبان منظمی مستقل از متن هست اما هرزبان مستقل از متنی منظم نیست.  
3)    گرامرهای حساس به متن:
 یک گرامر حساس به متن خواهد بود اگر و تنها اگر  هر قاعده آن به شکل زیر باشد:

α→ β      α ԑ(VᴜT) (+) , β ԑ(V ᴜ T) (+) , |α| <=|β|


این گرامر یک مرحله بالاتر از گرامر های مستقل از متن هست به صورت که دیگه محدودیتی در سمت چپ ( در مستقل از متن فقط باید یک متغیر وجود داشته باشد) قاعده نداریم و میتونیم در سمت چپ این نوع گرامر هم الفبا داشته باشیم و هم متغیر . البته همون طور که از شرط های  ذکر شده بعد از قاعده  که نوشته شده در میابیم که قاعده تهی  جزء قواعد گرامر های حساس به متن نیستند . بنابراین نمیتوان ادعا کرد که همه گرامر های مستقل از متن  گرامر هایی حساس به متن نیز هستند، بلکه میتوان گفت  هر گرامر مستقل از متن  بدون قاعده تهی  یک گرامر حساس به متن  است.
4)    گرامرهای بدون محدودیت:
یک گرامر بدون محدودیت ، گرامری است که هر قاعده اش به فرم زیر باشد:

Α→β    αԑ(Vᴜ T) (+) , β ԑ(V ᴜT)  ̽


این قاعده دیگه هیچ محدودیتی ندارد  و اگه یادتون باشه  جلسه گذشته موقعی که میخواستم گرامر را تعریف کنم یه همچین تعریفی گفته بودم .  

خب به پایان بحث امروزمون رسیدیم . امیدوارم خسته نشده باشید . مثال هایی که باهم حل کردیم در این دوجلسه  ، بررسیشون خالی از لطف نخواهد بود.  

شاد و موفق و سربلند باشید.
تا جلسه بعد خدانگهدار.

آنچه در نظریه خواهید دید....

جلسه اینده و جلسه بعد اون  میخوام  مثال های گرامر نویسی از روی زبان را براتون بگم. مثل عبارت های منظم  این بحث هم  مثال های زیادی براتون دارم  که گرامر نویسیتون را حسابی  عالی میکنه . مثال هامون از اسون شروع خواهد شد و کم کم شعله زیر مثال ها را زیاد خواهیم کرد.

کلمات کلیدی

محمدرضا احندآبادی
مهندس نرم افزار
کارشناسی مهندسی نرم افزار
مدرس دوره نظریه زبان ها و ماشین ها