حل مثال های عبارت های منظم جلسه دوم

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

عنوان :  جلسه دوم (آخر) بررسی مثال های عبارت منظم نویسی

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

این جلسه هم مثل جلسه قبل کمی طولانی خواهد بود پس امیدوارم مثل خازن زود دشارژ نشوید.

خب بریم سراغ ادامه مثال جلسه قبل:

L11={w ԑ{a,b}  ̽ / |w|=2k}

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

L11= ((a+b)(a+b))  ̽

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

L12= {wԑ{a,b}  ̽/ |w|=2k+1}

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

پس عبارت منظم این زبان خواهد بود:

L12=((a+b)(a+b))  ̽(a+b)

 

خب پنج مثال بعدی ما همه الفباشون {a,b}  ̽ wԑ  هست و من فقط شرط رشته های مورد پذیرش زبانو براتون خواهم نوشت.

{ رشته w با a شروع و به b ختم شود }= L13

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

L13= a (a+b)  ̽ b

{ رشته w با a  شروع شود یا به bb ختم شود}= L14

 

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

 

{رشته w  دارای حداقل یک a باشد } = L15

در مورد این مثال من باهاتون خیلی حرف دارم .

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

a(a+b)  ̽

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

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

حالا بعضیا اینجوری فکر میکنند که یه سمبل a را وسط میزارن بعد دو طرفشو b استار میزارن یعنی این شکلی :

 b  ̽ a b  ̽

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

این از چندتا دیدگاه غلط برای توصیف زبان. حالا بریم سراغ یه دیدگاه درست:

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

       L15= (a+b)  ̽ a (a+b)  ̽

خب این یه دیدگاه کاملا درست برای این زبان هست چون خواننده اجبار یکبار سمبل a را دارد و مابقی رشته هم به میل خودش میتواند باشد

اما من به این دیدگاه میگم دیدگاه ساده . چون راحت ترین نوع همین نوع هست . حالا میخوام یه توصیف دیگه از این زبان براتون بگم و به یه عبارت منظم دیگه برای این زبان برسم

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

پس تا این جا عبارت منظمی که من با این حرفا تولید کردم این شکلی خواهد بود ( البته هنوز عبارتم کامل نیست ):

L15= b  ̽ a …….

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

L15=b  ̽ a (a+b)  ̽

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

L15=(a+b)  ̽ ab  ̽

وجالب این هست هر سه عبارت منظمی که برای این زبان بدست اوردیم کاملا درست هست.

{ رشته w   با a شروع شود و طول آن زوج باشد} = L16

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

L16= a ((a+b)(a+b))  ̽ (a+b)

 

{ رشته w حداقل سه سمبل a را داشته باشد.}L17 =   

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

L18={ uwv / u,v,wԑ{a,b}  ̽  |u|=|v|=2}

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

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

(a+b)(a+b)

خب حالا اگه من دو بار این عبارت منظم را بنویسم میتونم بگم به خواننده اجازه دادم که دو تیکه رشته به طول زوج و به شکل دلخواه خودش تولید کنه یعنی من برای  قسمت u,v زبانم عبارت منظم اونو نوشتم حالا میاییم سراغ قسمت w .

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

L18= (a+b)(a+b)   (a+b)  ̽ (a+b)(a+b)

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

تمام حالت های رشته به طول دو با الفبای a,b به این صورت است: 

{aa,ab,ba,bb}

حالا من این موارد را مینویسم تا کاربر یکی از این موارد وانتخاب کنه و مابقی رشته دلخواه خودشو تولید کند.

پس صورت دوم این عبارت منظم به این شکل خواهد بود:        

L18=(aa+ab+ba+bb)  (a+b)  ̽  (aa+ab+ba+bb)


L19={ vwv / v,wԑ{a,b}  ̽ , |v|=2}

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

{طول رشته w زوج باشد و دارای دقیقا یک سمبل a باشد  /  ԑ{a,b,c} w}=L20

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

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

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

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

جواب تمرین ها، اخرین پنج شنبه سال ساعت 10 صبح در کانال حل تمرین قرار خواهد گرفت.

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

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

کلمات کلیدی

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