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

زبان زیر را در نظر بگیرید: A={<M> |M یک DFA بوده و هیچ رشته‌ای را که تعداد فرد یک را داشته باشد نمی‌پذیرد.}

نشان دهید که A تصمیم پذیر است.

اثبات:

راه حل اول:

نیاز داریم تا یک تصمیم گیرنده ی M را برای A بسازیم:

M = " در ورودی <M> را داریم که M یک DFA است:

1) DFA یِ O را چنان می‌سازیم که تمامی رشته‌هایی را که شامل تعداد فردی 1 است بپذیرد.

2) DFA یِ B را چنان می‌سازیم که L(B) = L(M( اشتراک L(0).

3) ماشین تورینگ MEDFA را با ورودی B اجرا می‌کنیم.

4) اگر MEDFA در حالت پذیرش قرار گیرد، A را می‌پذیریم، و الا A را رد می‌کنیم.