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

حل تمرین ۱-۱

تمرین

در شکل زیر دیاگرام حالت دو DFA به نام‌های M1 و M2 نشان داده شده است. به سوالات زیر در مورد این ماشین‌ها پاسخ دهید.

http://upload.wikimedia.org/wikipedia/commons/d/d0/R-jafargholi.jpg

الف – حالت شروع M1 را نام ببرید.

ب – حالت‌های پذیرش M1 را نام ببرید.

پ – حالت شروع M2 را نام ببرید.

ت – حالت‌های پذیرش M2 را نام ببرید.

ث – روش بررسی رشته ورودی aabb توسط ماشین M1 را مرحله به مرحله بنویسید.

ج – آیا M1 رشته aabb را می‌پذیرد؟

چ – آیا M2 رشته تهی (ε) را می‌پذیرد؟

حل

الف - q1
ب - q2
پ - q1
ت - q1 و q4
ث - q1,q2,q3,q1,q1
ج - خیر، زیرا دنباله حالت های aabb در Q که مجموعه محدودی از حالت هاست، موجود نیست و اگرچه r0=q1 یعنی در ابتدا در حالت شروع است، اما با توجه به تابع انتقال این ماشین که جدول آن به صورت زیر است و مشخص می کند که از هر حالت به چه حالتی می رود، می بینیم که در آخر در حالت q1 متوقف می شود، بنابراین پذیرفته نمی شود.

چ - بله، زیرا حالت شروع یکی از حالت های پذیرش می باشد.

b	a
q1	q2	q1
q3	q3	q2
q1	q2	q3