حل تمرین نظریه محاسبات/فصل اول/حل تمرین۱-۲
ظاهر
حل تمرین ۱ - ۲
تمرین
[ویرایش]توصیف رسمی ماشینهای M1 و M2 مربوط به تمرین۱-۱ را بنویسید.
حل
[ویرایش]برای ماشین M1 داریم :
M1 = (Q1,∑,δ1, q0 , F)
Q1={q1,q2,q3}
∑ ={a,b}
q0 ={q1}
F = {q2}
δ(q1,a)=q2
δ(q1,b)=q1
δ(q2,a)=q3
δ(q2,b)=q3
δ(q3,a)=q2
δ(q3,b)=q1
این زبان رشته هایی که به a ختم می شوند را می پذیرد.
برای ماشین M2 داریم :
M1 = (Q2,∑,δ2, q0 , F2)
Q1={q1,q2,q3,q4}
∑ ={a,b}
q0 ={q1}
F = {q1,q4}
δ(q1,a)=q1
δ(q1,b)=q2
δ(q2,a)=q3
δ(q2,b)=q4
δ(q3,a)=q2
δ(q3,b)=q1
δ(q4,a)=q3
δ(q4,b)=q4