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

تمرین

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

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

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

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

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

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

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

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

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

http://i43.tinypic.com/281vjut.jpg ghesmateh sahih]kh [ ghesmate j

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

<http://danial-h.persiangig.com/saeedeh/Presentation1.jpg http://upload.wikimedia.org/wikibooks/fa/e/e6/Tamrin_1-4.pdf

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

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

ر) {0,E}

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

http://www.savefile.com/files/2081507