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

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

سلام.محمدرضا احمدآبادی هستم با جلسه دوم و پایانی گرامر نویسی در خدمتتون هستم . امیدوارم از حال و هوای تعطیلات عید خارج شده باشید و راه رسیدن به اهدافتون را در پیش گرفته باشید.

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

شرط ما میگه رشته های مورد پذیرش این زبانباید تعداد سمبل a ان ها کمتر از تعداد سمبل های b  باشه. خب شرط حداقلی ما برای این زبان a=0 و b=1 خواهد بود . چون کمتر از این مقدار دیگه مجاز نیستیم که قرار بدیم. این زبان هم یه زبان نامحدود هست  گرامری که براش بنویسیم بازگشتی خواهد بود. پس گرامر ما خواهد شد:

S →AB

A →aAb|λ

B →bB|b


L14={anbm /n<=m}

 

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

 

S →aSb|A

A →bA| λ


L15={anbm/n ≠m}

 

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

 

S → aSb|A|B

A →aA|a

B →bB|b


L16={an bm cn /n,m>=0}

 

در این زبان تعداد a باید با تعداد c برابر باشه. تعداد b هم ازاد هست. این زبان لامبدا را میپذیره به خاطر شرطی که اورده و همین طور زبانی نامحدود هست .

 

S →aSc|A

A →bA|λ


L17={an bm ck / k=n+m}

 

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

 

S →aSc|A

A →bAc| λ


L18={an bm ck /m=n+k}

 

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

 

S → aSb|A

A →bAc| λ


L19={an bm ck / n+m=2k}

 

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

 

S →aaSc|A|abAc

A →bbAc | λ

 

حتما الان دارید میپرسید قسمت سوم متغیر شروع را برای چی نوشتم (  S →abAc) به این دلیل این قسمتو نوشتم که ما به ازای هر دو سمبل a,b باید یک سمبل c داشته باشیم . اگه یه موقع خواننده خواست طول سمبل a رشته اش فرد باشه و در جمع با سمبل b تعدادشون زوج بشه از این قانون میتونه استفاده کنه .

 

L20={an bm ck/ n+2m=k}

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

S →aSc|A

A →bAcc|λ


L21={ww(R) / w ԑ {a,b}̽ }

 

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

 

S →aSa|bSb| λ


L22={ww(R) / w ԑ{a,b} (+)}

 

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

 

S →aSa|bSb|aa|bb

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

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

نرمال سازی گرامر ها...

کلمات کلیدی

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