حل مثال های گرامر نویسی جلسه اول

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

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

L1={an / n>=0}


خب قبل از اینکه بریم سراغ حل این مثال میخوام براتون چندتا جمله کلیدی بگم پس خوب به حرفام توجه کنید.
برای نوشتن گرامر یک زبان مثل عبارت منظم نویسی هست یعنی هیچ قاعده و قانون خاصی نداره و این کار با تمرین زیاد براتون راحت خواهد بود اما این حرفا بین خودمون باشه چون تجربه شخصی خودم هست و هیچ پایه و اساس قانونی نداره . برای نوشتن گرامر یک زبان اولین کار به شرط حداقلی و حداکثری زبان توجه کنید  بعد ببینید زبان محدود هست یا نامحدود  بعد شروع کنید به ادامه کار. ( کم کم با دلیل این حرفایی که گفتم آشنا خواهید شد.)
دیگه بریم سراغ کار خودمون. این زبان عبارت منظمشو میشناسید چون قبلا کار کرده بودیم.  این زبان فقط سمبل الفبای a را دارا هست و شامل λ هم میشه .  این زبان یه زبان نامحدود هم هست پس میشه گرامر این زبان باید بازگشتی باشه.

S → aS


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

S →aS|λ


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

L2={an / n>0}


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

S → aS


خب اینکه درست  اما این گرامر که رشته تولید نمیکنه شما باید شرط خاتمه هم براش قرار بدهید. زبانمون شرط حداقلی اش چی بود؟ ایا باز هم به عنوان شرط خاتمه باید λ را در گرامر بنویسم ؟ یا نه؟
مسلما نه. این زبان دیگه رشته ای به طول تهی را نمیپذیره چون شرط حداقلی اش یک باید باشد . پس گرامر این زبان خواهد شد :

S →aS|a
L3={an /n=2k}


خب این زبان رشته های مورد پذیرشش رشته هایی به طول زوج از سمبل a هست . شرط حداقلی این زبان صفر . ( قضیه تحریم ها و زوجیت صفر را به یادتون بیاورید ) این زبان یک زبان نامحدود هست خب با این سه تفسیر دیگه نوشتن گرامر برامون راحت تر خواهدبود.
برای این که من بتونم درگرامر رشته a به طول زوج  تولید کنم باید این عبارتو بنویسم .

S →aaS


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

S → aaS | λ
L4={ an / n= 2k+1}


مقدار شرط حداقلی  ( شرط خاتمه) این زبان 1 است . زبان نامحدود پس گرامر ما بازگشتی خواهد بود.پس گرامر ما خواهد .  رشته های این زبان باید طولشون فرد باشد خب برای این که ما بتوانیم رشته بطول فرد تولید کنیم از همون قانون رشته به طول زوج استفاده میکنیم یعنی دوتایی های a را در یه قانون می اوریم و در انتها خواننده را مجبور میکنیم که موقعی که بخواهد رشته اش را خاتمه دهد یک سمبل a  در به انتهای رشته اش اضافه کند تا طول نهایی رشته فرد باشد. پس گرامر ما خواهد بود:

A → aaA|a


حتما دارید الان از خودتون میپرسید چرا محمدرضا  به جای متغیر S از متغیر A استفاده کرد؟ ببینید دوستان متغیر تعریف کردن تو گرامر به عهده گرامر نویس هست و اگه به دو جلسه گذشته مراجعه کنید خواهید دید من براتون یه سری قاعده که رعایت کردنش مرسوم هست در گرامر نویسی نوشته ام اما اونجا وهیچ کجای دیگه ای نخواهم گفت رعایت کردن این اصول اجباری هست.  بله من به عمد این گرامر را با متغیرA براتون نوشتم تا این حرفو بگم که یه موقع اگر جایی گرامری دیدید که متغیر شروع آن متغیری خلاف S هست اون موقع انگشت به دهن نمانید.

L5={an bm / n>=0 , m >=1}


برای نوشتن این گرامر شرط حداقلی در خود زبان گفته شده. خب معمولا علمای نظریه برای این زبان دوتا متغیر تعریف میکنند یکی برای تولید a وبا متغیر بعدی سمبل b را تولید میکنند. البته شکل درست این سخنم این طور باید باشه که برای نوشتن گرامر این زبان سه تا متغیر تعریف میشه یکی متغیر شروع و دوتا بعدی همون متغیر هایی هست که گفتم براتون. زبان ما یه زبان نامحدود هست پس گرامر این زبان باید بازگشتی باشه. خب من برای تولید سمبل a از متغیر A استفاده خواهم کرد و برای تولید سمبل b از متغیر B  استفاده خواهم کرد. یادتون هم باشه در این زبان سمبل های a باید همگی قبل از اولین سمبل b بیایند. برای این که من سمبل a را تولید کنم باید گرامرم به این شکل باشه :

A →aA|λ


فکر کنم دلیل نوشتن لامبدا را هم الان دیگه بدونید.  حالا میخوام سمبل b این زبانو تولید کنم پس باید گرامرم به این شکل باشه :

B →bB|b


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

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


جلسه گذشته من براتون گفتم اگه یه گرامر منظم ( فکر کنم یادتون نیومد منظورم خطی از راست و خطی از چپ هست) باشه پس زبان اون گرامر هم منظمه. حالا یه سوال این گرامر که من نوشتم ایا منظمه؟
دو خط اخر گرامر ما  خطی از راست هست  اما خط اول گرامر ما داره کارو خراب میکنه . چون ما در هر قانون برای گرامر های منظم باید حداکثر یک متغیر در طرف راست یه قانون داشته باشیم اما به خط اول توجه کنید AB دو تا متغیر هستن . پس این گرامر منظم نیست. خب سوال بعدی  حالا که این گرامر منظم نیست آیا زبان این گرامر هم منظم نیست؟
جواب این سوالو نمیتونیم از روی گرامر بدیم . چون برای یه زبان شکل های مختلف گرامر ممکنه وجود داشته باشه و شاید یکی از اون شکل ها منظم باشه اون وقت اون زبان منظم خواهد بود. پس عکس رابطه جلسه قبل برقرار نیست. خب این جمله کلی حالا برای این مثال جوابتون چیه ؟ این زبان منظم هست ؟( بزارید راحت تر براتون بگم برای این زبان عبارت منظم میتونید بنویسید؟)
نوشتن عبارت منظم این مثال به عهده خودتون من میخوام به جای عبارت منظم نوشتن این زبان شکل منظم گرامر این زبانو بنویسم.

S →aS|A
A →bA|b


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

L6={ an bm / n is odd , m is even}


در این زبان تعداد سمبل های a رشته های مورد پذیرشش باید فرد باشه و تعداد سمبل های b این رشته ها باید زوج باشه. خب شرط حداقلی سمبل a  ، 1 خواهد بود و شرط حداقلی سمبل b هم 0 خواهد بود.  زبان گرامر هم یه زبان نامحدود هست پس گرامر ی که برای این زبان بنویسیم بازگشتی خواهد بود.  برای تولید سمبلa از متغیر A استفاده خواهم کرد و برای تولید سمبل b از متغیر B استفاده خواهم کرد. چند مثال قبلی گرامر تولید رشته زوج و گرامر تولید رشته فرد را براتون گفته بودم. با استفاده از همون گرامر ها این گرامر را خواهیم نوشت.

S →AB
A →aaA|a
B →bbB|λ


این زبان همون طور که خودتون میدونید میتونیم با یه عبارت منظم بیانش کنیم پس این زبان منظمه اما گرامری که من براش نوشتم منظم نیست.
یه نکته: هیچ اجباری در نوشتن گرامر منظم برای شما نیست . اگر در یه سوال که گفته باشن برای زبان زیر یک گرامر بنویسید شما اگر از روش علمای نظریه هم عمل کنید هیچ اشکالی به کارتون وارد نیست فقط باید گرامری که مینویسید کاملا درست باشه یعنی نه رشته ای اضافه بر زبان تولید کنه و نه رشته ای کمتر.  اما چرا دارم بهتون میگم شکل منظم گرامر یه زبان مثلا فلان شکله. دلیل این کارم این هست که فرض کنید در یه سوال بهتون میگن چه تعداد از زبان های زیر منظم هستند؟ اونوقت میان چهارتا گرامر بهتون میدن  و در گزینه های تست چهارتا عدد براتون مینویسن.
اگه طراح سوال یه نفر مثل من باشه که به قول شاگردانم که بهم میگن بی رحم و... از این چهارتا گرامر یه دونه گرامر منظم بهتون میدم و سه تا گرامر غیر منظم . معمولا شما عادت به خوندن درست و کامل سوال ندارید فوری میایید سراغ گزینه ها و در جا جوابی که عدد 1 را نوشته میزنید این جاست که بی رحمی و حیله گری من پیدا میشه چرا؟ چون من در اصل سه تا از زبان هایی که تو سوال داده بودم منظم بوده اما یکیشو براتون شکل منظم گرامرشو نوشتم مابقیشو به صورت گرامر غیر منظم براتون نوشتم و در صورت سوال هم حرف از زبان زدم نه گرامر.   روش درست این کار اینه که شما ازروی گرامر زبان گرامر را بدست بیارید و ببینید اون زبان منظم هست یا نه؟
شکل منظم گرامر زبان ما خواهد بود:

S →aaS|aA
A →bbA|λ
L7={an bm / n+m=2k}


شرط این زبان داره میگه طول نهایی رشته های هدف این زبان باید زوج باشه. در مبحث عبارت های منظم گفته بودم برای اینکه جمع دوعدد زوج باشه یا باید هردوعدد زوج باشند و یا باید هردوعدد فرد باشند. من برای نوشتن گرامر این زبان به غیر از متغیر شروع به دوتا متغیر برای اینکه هرکدوم از سمبل a و b را به طول زوج تولید کنم نیاز دارم و به دوتا متغیر دیگه هم احتیاج دارم تا هرکدوم از سمبل هارا به طول فرد تولید کنم . خب برای طول زوج از متغیر های A و B استفاده خواهم کرد و برای طول فرد هر کدوم از سمبل ها از C و D استفاده میکنم.  قسمت اول گرامر ما خواهد شد:

S → AB
A→aaA| λ
B → bbB| λ


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

S → CD
C →aaC|a
D →bbD |b


حالا ما باید این دوقسمتو در قالب یک گرامر بیان کنیم پس گرامر نهایی ما خواهد شد:

S →AB | CD
A →aaA| λ
B → bbB | λ
C →aaC|a
D →bbD|b


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

L8={anbn / n>=0}


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

L8= a  ̽ b  ̽


الان اینجا جا داره که در جوابتون عرض کنم زهی خیال باطل. چرا؟  
زبانی که براتون نوشتم  داره میگه باید سمبل های a و b   تعدادشون باهم برابر باشه و اینکه سمبل های a باید قبل از اولین سمبل b در رشته بیاییند. خب عبارت منظمی که به من گفتید شرط دوم را داره اما شرط اول چی؟ من اگر خواننده ی باحالی باشم اونوقت هردو استار را عدد یکسان در نظر میگیرم اما از اون جایی که من خواننده ضدحال زنی هستم باید بهتون بگم یکی از حالتهای عددهایی که میتونم جای استار بزارم این هست که مساوی باشه و حالت های دیگه شاید برابر نباشه.  خب پس این عبارت منظم درست نیست .  شما هر عبارتی که به ذهنتون میرسه را امتحان کنید خواهید دید که یه جای کار مشکل خوهدداشت.
 خب این از دلیل اینکه چرا زبان مورد نظرمون منظم نیست اما بحث ما در مورد گرامر نویسی هست . شرط این زبان  n>=0 هست پس میشه گفت رشته تهی را میپذیره . این از شرط پایانی این زبان . از طرفی هم این زبان یه زبان نامحدود هست پس قواعدی که بخواهیم براش بنویسیم باید بازگشتی باشه.  حالا من چطور در گرامر باید مساوی بودن a و b را کنترل کنم؟ تنها راهی که میشه تعداد مساوی بودن این دو سمبل را در کنترل کرد این هست که هر دو سمبل را در یه قاعده بیارم اما چطوری؟

1)    S →abS|λ
2)    S →Sab|λ
3)    S →aSb|λ


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

S →abS →ababS→ abab


با استفاده از اشتقاق ، دوبار به جای متغیر S قانون مربوطه اش را نوشتم  و دفعه سوم به جای متغیر S از قانون دوم یعنی لامبدا  استفاده کردم و این رشته تولید شد . خب در این رشته آیا همه سمبل های a قبل از اولین سمبل b  قرار گرفته؟    پس این گرامر برای این زبان درست نیست.
در گرامر دوم :

S →Sab →Sabab →abab


خب این گرامر هم به همون دلیل گرامر قبلی  ، گرامر درستی برای این زبان نیست.
در گرامر سوم:

S →aSb →aaSbb →aabb


در هر سه گرامر تعداد a و b باهم مساوی بود اما در گرامر سوم شرط بعدی ما هم رعایت شده بود یعنی تمام سمبل های a باید قبل از اولین سمبل b قرار گرفته باشند.

L9={an bn / n>=1}


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

L10={a(2n) b(2n) / n>=0}


روبروی این زبان عبارت تمرین سوم را بنویسید.

L11={a(2n+1) b(2n+1) /n>=0}


روبروی این زبان عبارت تمرین چهارم را بنویسید.

L12={ a(n) b(2n) / n>=0}


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

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

L7={an bm / n+m=2k}


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

S →aaS|aA|B
A →bbA|b
B →bbB| λ

L9={an bn / n>=1}

تفاوت زبان این مثال با مثال اخر جلسه نهم در این هست که این زبان  λ را نمیپذیره. همین.

S →aSb|ab
L10={a(2n) b(2n) / n>=0}


این زبان هم تقریبا حرف همون زبان را داره میزنه با این تفاوت که تعداد سمبل a,b باید هرکدوم زوج باشندو لامبدا هم میتونه عضو رشته های این زبان باشه. پس گرامر ما خواهد شد:

S →aaSbb| λ
L11={a(2n+1) b(2n+1) /n>=0}


تفاوت این زبان با زبان  L10 در نپذیرفتن لامبدا هست  پس خواهیم داشت:

S →aaSbb|ab
L12={ a(n) b(2n) / n>=0}


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

S →aSbb|λ

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

کلمات کلیدی

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