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

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

سوال :

فرض کنید F زبانی است که شامل رشته های {0,1} می باشد که هیچ جفت یکی(1) در آن وجود ندارد به طوری که بین آن ها تعداد فرد علامت قرار داشته باشد. دیاگرام حالت DFA با 5 حالت که F را تشخیص می دهد به دست آورید. (بهتر است ابتدا NFA چهارحالته را برای مکمل F پیدا کنید)


جواب :

DFA حاصل به صورت زیر خواهد بود :

G736-26.GIF