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

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

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

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

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

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

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

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

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

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

حالا برای این که بدونید عبارت منظمی که برای اون زبان به ذهنتون رسیده درست هست یا اشتباه تنها یک راه دارید اونم این هست که شما عبارت منظمو برای خودتون روی یک کاغذ مینویسید و رشته هایی که اون عبارت منظم تولید میکنه را ایده اش را به دست میاورید. اگر این رشته ها بدون هیچ کم یا زیادی عین رشته هایی باشد که زبان اصلی تولید میکند نتیجه بگیرید که  عبارتی که نوشته اید درست هست اما 1- اگر بعضی از رشته های زبان را تولید نکرد یا 2- علاوه بر رشته های زبان رشته های اضافه هم این عبارت منظم تولید کرد( حتی یک رشته) یا 3- کلا هیچ کدوم از رشته های تولیدی زبانو تولید نکرد نتیجه بگیرید که این عبارتی که برای این زبان نوشتید اشتباه هست.

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

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

{L3={a(n) / n>=2

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

 *L3= aaa 

{L4={ a(n) / n=2k

 

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

 

شاید  به این عبارت رسیدید:

* L4= a  ̽ a 

دوتا سمبل a نشانه زوج بودن هست . پس الان دارید فکر میکنید این رشته های مورد نظرو تولید میکنه.

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

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

پس این عبارتی که به ذهنتون رسیده اشتباه هست. خب پس عبارت منظم درست چی میشه؟

 * (L4=(aa

بعضیا شاید این عبارت به ذهنشون رسیده . ببینیم درست گفتن یا نه؟

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

{ L5={ a(n) / n=2k+1

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

پس قلم و کاغذتون را دست بگیرید وروبروی این زبان عبارت وحشتناک تمرین اول را یادداشت کنید.

{ L6={a(n) /n mod 3>0

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

اگر یه عدد صحیحی بر 3 تقسیم بشه باقیمونده اون تقسیم چه عددهایی خواهد بود؟

     بله جوابتون درسته باقیمانده یا صفر خواهد بود یا یک ویا دو.

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

برای این که عبارت منظم ما رشته هایی تولید کنه که باقیمانده اش به عدد 3 یکی بیشتر باشه  عبارت ما به این شکل خواهد بود:

(aaa)  ̽ a

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

اما ایا کار در این جا به پایان میرسد ؟

باید بگم خیر . چون با این عبارت منظمی که ما نوشتیم فقط رشته هایی تولید میشوند که باقیماندشون 1 خواهد بود. اما من خواننده میخواهم رشته هایی تولید کنم که باقیماندشون بر 3 ، 2 شود.

حالا باید یه عبارت منظم برای رشته هایی که باقیمانده اش به عدد 3، 2 باشد را بنویسیم که عبارت مورد نظر به این شکل خواهد بود:

(aaa)  ̽ aa

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

حالا به نظرتون کار به پایان رسید؟

باید بگم  خیر . باز دیگه چرا؟؟؟؟

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

اما خارج از شوخی ، شاید پیش خودتون بپرسید چرا کار تموم نشده هنوز؟

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

پس خواهیم داشت:

L6= (aaa)  ̽ a +(aaa)  ̽aa

دقت کنید قبلا هم موقع تعریف عملگرهای عبارت های منظم  گفته بودم (+) یعنی انتخاب بین یکی . نه هردو.

شکل دوم عبارت منظم این زبان:

L6=(aaa)  ̽ (a+aa)

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

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

L7={a(n) / n mod 3 =0}

زیریادداشت تمرین اولتون بنویسید: اینم از تمرین دوم، مثل این که ضدحال های محمدرضا تمومی نداره.

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


 

L8={ w ԑ{a,b}  ̽/ |w| >=0}

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

عبارت منظم این زبان میشه:

L8= (a+b)  ̽

چند مثال براتون مینویسم . فرض کنید من میخواهم رشته های  λ,a,b,ab,bba را تولید کنم . خب برای تولید لامبدا کافیه من استار را صفر در نظر بگیرم . انوقت لامبدا تولید میشود. برای تولید رشته a کافیه من استار را یک فرض کنم و چون استار یک است من میتوانم از بین سمبل های a,b یکی را انتخاب کنم  فقط یک بار که ان هم سمبل a خواهد بود. برای تولید رشته b مثل رشته a عمل خواهم کرد با این تفاوت که من سمبل b را انتخاب خواهم کرد . برای تولید رشته  ab کافیه من استار را دو فرض کنم ودر مرحله اول سمبل a را انتخاب کنم و در مرحله دوم سمبل b را انتخاب کنم . برای تولید رشته bba کافیه من استار را سه فرض کنم و در مرحله اول سمبل b را انتخاب کرده ، در مرحله دوم هم سمبل b را انتخاب کنم و در مرحله اخر هم سمبل a را انتخاب کنم .

با این عبارت منظم میتوان تمام رشته های روی الفبای a,b را تولید کرد.

L9={a(n) b(m) / n=2k , m=2q+1}

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

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

L10={ a(n)b(m) / زوج باشد  n+m}

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

اگر هردوسمبل a,b زوج باشند عبارت منظم ما این طوری خواهد بود:

(aa)  ̽ (bb)  ̽

واگر هردوسمبل a,b با هم  در یک رشته بخواهند به تعداد فرد باشند عبارت منظم ما خواهد بود:

(aa)  ̽ a (bb)  ̽ b

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

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

L10= (aa)  ̽ (bb)  ̽  + (aa)  ̽a (bb)  ̽ b

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

L10= (aa)  ̽ (λ+ab) (bb)  ̽

حالا با همدیگه بررسی میکنیم ببینیم ایا درست هست یا نه؟

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

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

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

شاد و موفق و سربلند باشید .

تا جلسه بعد خدانگهدار.

کلمات کلیدی

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