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

حل تمرین 1-21

تمرین

با توجه به حل تمرین 1.20 یک توصیف رسمی برای ماشینهای T1 و T2 که در مساله 1.19 داده شده ارائه کنید.

حل

T1:
(Q, Σ, Γ, δ, q1, F)
Q = { q1, q2 }
Σ = { 0, 1, 2 }
Γ = { 0, 1 }
F = { q1 }
δ(q1,0)=(0,q1) , δ(q1,1)=(0,q1) , δ(q1,2)=(1,q2)
δ(q2,0)=(0,q1) , δ(q2,1)=(1,q2) , δ(q2,2)=(1,q2)
T2 :
(Q, Σ, Γ, δ, q1, F)
Q = { q1, q2, q3 }
Σ = { a, b }
Γ = { 0, 1 }
F = { q3 }
δ(q1,a)=(1,q2) , δ(q1,b)=(1,q3)
δ(q2,a)=(1,q3) , δ(q2,b)=(0,q1)
δ(q3,a)=(0,q1) , δ(q3,b)=(1,q2)