حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-41

حل تمرین 1-41

تمرین

مجموعه D زیر را در نظر بگیرید.

{w شامل تعداد مساوی از زیر رشته های 10 و 01 می باشد.|D = { w

بنابراین 101 عضو D می باشد چون 101 دارای یک زیررشته 10 و یک زیررشته 01 است ولی 1010 عضو نیست چون دارای دو عدد 10 ولی دارای یک عدد 01 می باشد. نشان دهید که D منظم است.

حل

برای اثبات منظم بودن یک زبان کافی است که DFA آن را رسم کنیم. در شکل زیر DFA زبان D رسم شده است.

Najafi 852161028