amoozesh.org
amoozesh.orgPersian Tutorials
ورود
ایجاد: 1398/10/4 21:07 - ویرایش: 1398/10/19 10:10

آموزش تبدیل DFA به عبارت منظم

برای تبدیل یک ماشین متناهی قطعی DFA به عبارت منظم (Regular Expression) روش های متفاوتی وجود دارد، در این آموزش ما از روش حذف حالت ها (State Elimination Method) استفاده می کنیم.

روش حذف حالت ها (State Elimination Method)

قانون اول

وضعیت های مرده را حذف می کنیم، وضعیت هایی که هیچ مسیری به حالت پایانی ندارند را وضعیت مرده می گویند.

در مثال بالا C یک وضعیت مرده است، و قبل از هر چیز آنرا حذف می کنیم.

قانون دوم

هیچ یالی نباید وارد حالت اولیه شود.

در صورت وجود یال ورودی در نود اولیه، A در شکل بالا، یک حالت اولیه دیگر ایجاد کرده و آن را به A وصل می کنیم.

قانون سوم

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

در صورت وجود یال خروجی از وضعیت پایانی، به عنوان مثال B در شکل بالا، یک حالت پایانی دیگر ایجاد کرده و B را به آن وصل می کنیم.

قانون چهارم

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

در صورت وجود بیش از یک حالت پایانی همانند شکل بالا، یک حالت پایانی جدید ایجاد کرده و حالت های پایانی قبلی را به آن وصل می کنیم.

نکته

حال با ذکر چند مثال کاربردی تبدیل ماشین های متنهای قطعی (DFA) به عبارات منظم (Regular Expression) را به صورت مفصل نشان خواهیم داد.

مثال های تبدیل DFA به عبارات منظم

مثال

همانطور که در مثال بالا مشاهده می شود، به وضعیت شروع A یال 1 وارد شده و از وضعیت پایانی B یک یال خارج شده است

مثال

B یک وضعیت مرده است پس ابتدا آنرا حذف می کنیم، سپس بر اساس قوانین ذکر شده یک حالت شروع و یک حالت پایان جدید به آن اضافه می کنیم

تمرین

3 نمودار DFA فوق با هم برابرند، یال های هم جهت را یکی کرده و با هم جمع می کنیم، در مثال فوق یال a و b هم جهت هستند، از حالت A خارج شده و به خود حالت A وارد شده اند.

مثال

کلیه رشته های الفبای {a,b} که به حرف a ختم می شوند.

در ماشین بالا اگر ابتدا A را حذف کنیم نتیجه پایین بدست می آید که با نتیجه بالا یکسان است

برای این زبان میتوان یک NFA نیز طراحی کرد که آن هم با نتیجه بالا یکسان است ولی ساده تر است.

(b+aa*b)*aa* b*a(a+bb*a)* (a+b)*a

عبارت های منظم بالا همه با هم برابرند

در بالا ماشین سمت چپ DFA و ماشین سمت راست NFA معادل یکدیگر می باشند

نتیجه گیری: برای یک زبان خاص چندین عبارت منظم و ماشین وجود دارد

تمرین

تمرین

تمرین

وضعیت D به هیچ وضعیت پایانی راه ندارد و یک وضعیت مرده است، پس حذف می شود.

تمرین

مثال

مثال

مثال

مثال

مثال

مثال