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

حل تمرین 1-22

تمرین

تعریف غیر رسمی تراگذر با حالت محدود را در تمرین 1.19 مطالعه کنید. دیاگرام حالت یک FST با رفتار زیر را رسم کنید. الفبای ورودی و خروجی آن {0,1} بوده و خروجی آن در مورد موقعیت های زوج مشابه نماد ورودی و در موقعیت های فرد معکوس می‌شود. برای مثال برای ورودی 0000111 ، خروجی باید 1010010 باشد.

حل

دیاگرام حالت مطلوب به صورت زیر خواهد بود که حالات را می توان غیرپذیرش هم در نظر گرفت.

(Q, Σ, δ, q1, F)
Q = { q1, q2 }
Σ = { 0, 1 }
Γ = { 0, 1 }
F = { q1, q2 }
δ(q1,0)=(1,q2) , δ(q1,1)=(0,q2)
δ(q2,0)=(0,q1) , δ(q2,1)=(1,q1)