∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinesini tanımlayınız?

∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinesini tanımlayınız?

C diline ait ifadeleri kabul eden, aksi ifadeleri reddeden bir Turing makinesi tasarlayacağız.
İfadenin ortasında # işareti var ve #’in sağ ve solundaki ifade aynı olmak zorundadır.

Çözüm yaklaşımı: # işaretinin sağında ve solunda zikzak yaparak çözüme ulaşabiliriz.
İfadenin içerisinde # işareti yoksa ret,
# işareti varsa ve #’in sağındaki ve solundaki sembollerin sayısı farklıysa ret,
aynıysa #’in sağındaki ve solundaki sembollerin dizilişi farklıysa ret, aynıysa kabul durumuna geçer.

w#w

Q (Durumlar)= {q1,q2,q3,q4,q5,q6,q7,q8,qaccept},
Girdi alfabesi= {0,1,#}
Teyp Alfabesi = {0,1,#,x,null}

011000#011000 girdisi için adımların simülasyonu:

w-sharp-w

Etiketler: , ,

Yorum Yapın