حل تمرین نظریه محاسبات/فصل اول/حل تمرین ۱-۴
این صفحه یا کتاب ممکن است به تصویرهای بیشتری نیاز داشته باشد. تصویرها برای راحت تر رساندن مفاهیم کمک میکنند. میتوانید تصویرهایی را از ویکیانبار پیدا کنید و در ویکیکتاب استفاده کنید. اگر خودتان شخصا تصویری را ایجاد کردهاید ابتدا با پروانه مناسب آن را بارگذاری و سپس استفاده کنید. هنگامی که نگارههای مناسب افزودید این الگو را بردارید. البته حتی پس از برداشتن این الگو نیز میتوانید کتاب و نگارههای آن را ویرایش کنید؛ در مورد چگونگی ویرایش کتاب در صفحه بحث به بحث بپردازید. اگر پرسشی دارید در میز تحریر بپرسید. |
تمرین
[ویرایش]برای تشخیص هر کدام از زبان های زیر دیاگرام حالت یک 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}
برای مشاهده قسمتهای د-ذ-ر به آدرس زیر مراجعه کنید (دانلود)