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

حل تمرین ۱ - ۲

تمرین

توصیف رسمی ماشین‌های 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