حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۴۸

حل تمرین۱-۴۸

تمرین:

فرض کنید الفبای Σ به صورت { 0,1}= Σ و زبان D به صورت { w | wشامل رشته هایی که تعداد وقوع رشته های 01 و 10 در آنها برابر باشد. } =D باشند. بنابراین 101 عضو D است زیرا 101 شامل یک 01 و یک 10 می باشد ولی 1010 عضو D نیست چون 1010 شامل دو 10 و یک 01 است.نشان دهید که D یک زبان منظم است.

حل:

برای اینکه ثابت کنیم D یک زبان منظم است, باید یک DFA برای آن رسم کنیم.