ایجاد: 1398/10/4 21:07 - ویرایش: 1399/3/30 21:31

A A

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

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

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

قانون اول

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

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

قانون دوم

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

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

قانون سوم

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

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

قانون چهارم

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

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

نکته

در پروسه ایجاد عبارت منظم، کاهش وضعیت ها را تا جایی ادامه می دهیم که تنها 2 حالت باقی بماند، اولیه و پایانی
روش توضیح داده در این آموزش برای ماشین های متنهای غیر قطعی (NFA) و ماشین های غیر قطعی با λ نیز دقیقا درست عمل می کند.

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

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

مثال: {a*}

تمرین: تمامی حالات الفبای {a,b}

مثال: {a(ba)*}

مثال: همواره حرف a قبل از b بیاید؟ {aⁿ b^m : n, m >= 0}

ساده سازی

a*(λ+bb*)a*b*

برای ساده سازی عبارات منظم به این صفحه مراجعه کنید.

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

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

(a*b)*aa*
(a*b)*a*a

(a*b)*a*a
(a+b)*a

برای این زبان میتوان یک NFA نیز طراحی کرد.

(b+aa*b)*aa*

b*a(a+bb*a)*

(a+b)*a

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

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

تمرین: با aa تمام شوند.

(b+aaa*b+a(b+aa*b))*aaa*
(b+aaa*b+aa*b)*aaa*

(b+aaa*b+aa*b)*aaa*
((λ+aaa*+aa*)b)*aaa*

((λ+aaa*+aa*)b)*aaa*
(a*b)*aaa*

(a*b)*aaa*
(a*b)*a*aa

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

تمرین: با a شروع و با a خاتمه یابد.

ساده سازی

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

تمرین: {a(b,c,d)}

تمرین: شامل زیر رشته ab نباشد؟

b*(λ+aa*)
b*a*

تمرین: شامل زیر رشته ab باشد؟

bb*aa*b(a+b)*

تمرین: شامل زیر رشته aab نباشد؟

(b+ab)*(λ+a(λ+aa*))
(b+ab)*(λ+aa*)

(b+ab)*(λ+aa*)
(b+ab)*a*

تمرین: شامل زیر رشته aab باشند؟

(b+ab)*aaa*b(a+b)*
(b+ab)*a*aab(a+b)*

حذف از چپ

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

b*(abb*)*aaa*b(a+b)*
(b+ab)*aaa*b(a+b)*

شامل زیر رشته aaa باشد؟

(b+aab+a(b+ab))*aaa(a+b)*
(b+aab+ab+aab)*aaa(a+b)*

(b+aab+ab+aab)*aaa(a+b)*
(b+aab+ab)*aaa(a+b)*

شامل زیر رشته aaa نباشد؟

(b+a(b+ab))*(λ+a(λ+a))
(b+a(b+ab))*(λ+a+aa)

(b+a(b+ab))*(λ+a+aa)
(b+ab+aab)*(λ+a+aa)

تمرین: {bⁿa^mb^k : n,m,k >= 0}

b*(λ+(aa*(λ+bb*)))
b*(λ+aa*b*)

b*(λ+aa*b*)
b*(a*b*)

b*a*b*

تمرین: abc به ترتیب بیایند.

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

a*((λ+bb*)+(c+bb*c)c*)
a*(b*+(c+bb*c)c*)

a*(b*+(c+bb*c)c*)
a*(b*+b*cc*)

a*(b*+b*cc*)
a*(b*(λ+cc*))

a*(b*(λ+cc*))
a*(b*c*)

a*(b*c*)
a*b*c*

مثال

مثال: تعداد b ها در آن زوج باشد؟

(a+ba*b)*

مثال: تعداد ab ها و ba ها با هم برابر باشند؟

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

مثال: تعداد زوج زیر رشته ab را بپذیرد؟

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

تمرین

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

مثال: تعداد a ها و b ها فرد باشد.

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