بهینه سازی ماشین های DFA

1396/1/12 محمدرضا احمدآبادی 2930


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

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

این روند شامل دو مرحله است :
1-  در ابتدا حالتهای غیر قابل دسترس ماشین را یافته و حذف میکنیم.( در مرحله دوم آنهارا به حساب نمی آوریم)
نکته: یک حالت غیرقابل دسترس حالتی است که به هیچ عنوان نتوان از حالت شروع به آن رسید.
2-  در این مرحله یک مجموعه شامل دو پارتیشن  تعریف میشود ، یکی پارتیشن حالت های غیرپایانی و دیگری پارتیشن حالت های پایانی . سپس رفتار حالت های درون یک پارتیشن را به ازای سمبل های الفبایی یکسان بررسی میکنیم.  منظور از رفتار یکسان  دو حالت به ازای یک سمبل الفبا انتقال آن دو حالت با آن سمبل به یک پارتیشن یکسان است  و منظور از رفتار متفاوت  انتقال به پارتیشن های متفاوت است . پس از اینکه رفتار تک تک حالت ها با هر یک از سمبل های الفبا بررسی شد ، حالت هایی از یک پارتیشن را که رفتار یکسانی دارند در مرحله بعد نیز در یک پارتیشن نگه میداریم وآن هایی که رفتار متفاوتی دارند جدا میکنیم. این روند را تا جایی ادامه میدهیم که نتیجه یک مرحله با مرحله قبلی یکسان شودویا همه پارتیشن ها تک عنصری شوند. در پایان حالت هایی که درون یک پارتیشن باشند حالت های معادل یا تمایزناپذیر مینامیم. در ماشین بهینه میتوانیم  به جای چند حالت معادل آن که یک حالت است قرار دهیم
ماشین بهینه از روی ماشین اولیه وبا کاهش حالت های معادل به دست می آید.
 
مثال) تعداد حالت های آتاماتا زیر را کمینه نموده و زبان آن را به دست آورید.

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

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

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

P={{q0,q1,q2,q3},{q4}}


حالا باید رفتار اعضای هر مجموعه را بررسی کنیم .  شما روی کاغذ این پارتیشن را بنویسید و برای راحتی کارتون بالای این پارتیشن حرف های من را با علائم بنویسید  تا در انتها راحت تر به نتیجه برسید.( شبیه یک جدول فرضی)

حالت q0 با سمبل 0 به حالت q2 میرود که همین حالت q2 در پارتیشن 1 قرار دارد. شما بالای p به صورت ستونی الفباهای ماشین را بنویسید حالا روبروی سمبل 0 و بالای q0 بنویسید 1.  منظور من این است حالت q0 با سمبل 0 به پارتیشن 1 میرود. مابقی حالت هارا این طوری باید تعیین تکلیف کنیم.

حالت q1 با سمبل 0   به حالت q2 که در پارتیشن 1 قرار دارد میرود. حالت q2وq3 هم به همین ترتیب با سمبل 0 به پارتیشن 1 انتقال دارند. حالت q4 با سمبل 0 به خودش انتقال دارد که در پارتیشن دوم قراردارد پس بالای حالت q4 و روبروی سمبل 0 مینویسیم 2.  این از بررسی سمبل 0 هر چهار حالت حالا باید سمبل 1 را بررسی کنیم.

حالت q0 با سمبل 1 به حالت q3 میرود که در پارتیشن 1 قرار دارد پس خواهیم نوشت 1. حالت q2با سمبل 1  به حالت q4 انتقال دارد و q4 در پارتیشن 2 قرار دارد پس بالای حالت q1 و روبروی سمبل 1  مینویسیم 2 . حالت های q2,q3 هم به همین ترتیب همان طور که از شکل پیداست با سمبل 1 به حالت q4 انتقال دارند پس بالای این حالت ها  و روبروی سمبل 1 مینویسیم 2. حالت q4 با سمبل 1 به خودش انتقال دارد پس بالای این حالت و روبروی سمبل 1 مینویسیم 2.

اگر به عناصر پارتیشن 1 توجه کنیم میبینیم که حالت های q1,q2,q3 با سمبل های 0و1 رفتار یکسانی دارند اما حالت q0 با سمبل 1 رفتار متفاوتی نسبت به حالت های دیگر این پارتیشن دارد. پس این پارتیشن را میشکنیم به دو پارتیشن .پس پارتیشن های ما خواهد بود:
 

P={{q0},{q1,q2,q3},{q4}}

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

حالت q0 با سمبل 0و1 به حالت های q1وq3 انتقال دارد که هردو در پارتیشن 2 هستند . پس به ازای 0و1 خواهیم نوشت 2.
حالت q4 هم با سمبل 0و1 به خودش انتقال دارد که در پارتیشن 3 قرار دارد پس بالای این حالت  و روبروی سمبل های 0و1 خواهیم نوشت 3.
حالت های q1,q2,q3 به ازای سمبل 0 به پارتیشن خودشون (2) انتقال دارند و به ازای سمبل 1 به پارتیشن 3 انتقال دارند پس رفتار همه عناصر پارتیشن دو یکسان هست و احتیاجی به شکستن پارتیشن دوم نخواهد بود . پس خواهیم داشت:

 

P={{q0},{q1,q2,q3},{q4}}

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

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

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

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

دانلود PDF قسمت هفدهم آموزش نظریه زبان ها و ماشین ها

کلمات کلیدی

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