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

[برای تشخیص هر کدام از زبان های زیر دیاگرام حالت یک DFA را رسم کنید.در تمام موارد الفبا {0و1} است.

الف) تمام رشته هایی که با 1 شروع شده و به 0 ختم می شوند.

ب)تمام رشته هایی که حداقل سه عدد 1 دارند.

پ)تمام رشته هایی که شامل زیر رشته 0101 هستند.یعنی رشته هایی که به صورت w=x0101y که X و Y دو رشته دلخواه باشند.

ت)تمام رشته هایی را که حداقل طول آن برابر 3 بطوریکه سمبل سوم آن برابر 0 باشد.

ث)تمام رشته هایی را که اگر سمبل اول آن برابر 1 بود طول آن برابر زوج باشد و اگر 0 بود طول آن برابر فرد باشد.

ج)تمام رشته هایی را بپذیرد که زیر رشته 110 را نداشته باشند

چ)تمام رشته هایی که شامل زیر رشته 110 نباشند

ح)رشته هایی که حداقل 5 نماد طول دارند

[۱]

[۲]

توجه: برای حل قسمت های فوق به آدرس های زیر مراجعه نمایید

[۳]

[۴]

د) تمام رشته هایی که در موقعیت زوج آن رشته ها نماد 1 قرار دارد

ذ) تمام رشته هایی که حداقل دو عدد 0 و حداقل یک عدد 1 دارند

ر) {0,E}

برای مشاهده قسمتهای د-ذ-ر به آدرس زیر مراجعه کنید (دانلود)

[۵]