Yazan : Şadi Evren ŞEKER
Turing makinesini anlattığım bu yazıda gelen bir soru üzerine, sorunun cevabını yayınlıyorum. Soruyu soran, onur bey, eşit sayıda a ve b bulunan bir kelimeyi kabul eden Turing makinesi tasarımı istemiş.
Şimdi bu soru iki türlü anlaşılabilir. Kolay olanı anbn şeklinde a ve b harflerinin sırayla gelmesi. yani n tane a harfinin n tane b harfinden önce gelmesi. Tabi bir de eşit sayıda a ve b olması ve bunların karışık dizilimde olması mümkün.
Yani ilk durumda aaabbb şeklindeki kelimeleri kabul ederken ikinci durumda aabbab şeklindeki kelimeleri de kabul etmesini bekleyebiliriz.
ilk durum için basitçe kelimenin başından bir a sildiğimizde, kelimenin sonundan da bir b silicez. Dolayısıyla a ve b harfleri aynı anda biterse eşitler, şayet birisi önce biterse eşit değiller diyeceğiz.
ikinci durum ise biraz daha zor, kelimenin başından bir harf silip (örneğin a) sonra tersi olan harfi (bu durumda b) kelimenin yine başından ilk gördüğümüz durumda silmemiz gerekiyor. Ancak bu silme işlemini kaydırarak yapmamız gerekiyor.
Örnek üzerinden anlatacak olursam :
-abaaaabbbb- şeklinde bir kelime olsun:
a ve hemen sonra kelimede gelen ilk b siliniyor
—aaaabbbb- halini alıyor ve devam ediyoruz:
—-aaabbbb- şimdi bir a sildik ve bir de b silmemiz gerek. Makinemiz ilk b’yi bulup silecek:
—-aaa-bbb- fakat görüldüğü üzere kelimenin içinde boşluk oldu bunu düzeltmek için kaydırıyoruz:
—-aaabbb– ve böylece devam ediyor.
Burada boşluk oluşması ve kaydırma probleminin çözümü için ilave bir sembol kullanılabilir. Örneğin c sembolü kullanacak olalım. ilk silmeden sonra
-ccaaaabbbb- şeklinde ilk a ve b silindiler
-cccaaacbbb- şeklinde ikinci silme gerçekleşti ve bu şekilde devam ediyoruz. Ta ki bütün kelime c olana kadar. Şayet b veya a önce biterse o zaman eşit değil diyebiliriz.
Yukarıda, iki problemin de çözümünü anlattım ama kolay olanının makinesini çizip adım adım yukarıdaki yazıya ekleyeceğim. Eh zor olanını da artık siz yaparsınız 
Çözüm:
Örnek kelimemiz aabb olsun. Bu örneği çözerken sırasıyla bir a harfinin yerine x bir de b harfinin yerine y koyacağız. En sonunda, bütün a’lar x ve bütün b’ler y ile değişmiş olacak ve makinemizde hiç a ve b kalmadıysa kabul edeceğiz. Şayet a sayısı b’den fazlaysa, o zaman hala x harfine dönmeyen a’lar bulunacak veya benzer şekilde b harfi a’dan fazla ise bu durumda da hala y harfine dönmeyen b’ler bulunacaktır. Bu durumda bantta a veya b harfi kalmışsa, makinemiz bu kelimeyi kabul etmeyecektir.
Yukardaki Turing makinesi tasarımı, problemimizi çözer. Bu çözümü bir örnek üzerinden adım adım görelim.
Örneğimiz aabb kelimesi olsun ve bakalım makinemiz bu kelimeyi kabul edecek mi.
Kelimenin ilk harfinde, makinemiz q0 durumundadır (state). Bu durumda banttan a okuduğu için q1 durumuna geçer ve banda x koyar.
Makinemiz, a gördüğü üzere bandı sağa (R) sarmaya devam edecek ve b görünce q2’ye geçecektir.
Şimdi makinemiz b gördüğü durum olan q2 geldi ve geri sarmaya başlıyor. Bu işlem x görene kadar devam edecektir ve x görünce q0 durumuna dönecektir.
X harfini görünce sağa sardık ve gördüğümüz ilk a harfini x ile değiştirerek makinenin şimdiye kadar yaptığı işlemleri bir kere daha tekrar etmeye başladık.
Sonuçta makinemiz, bir a harfini x ile değiştirmiştir ve bir b harfini de az önce olduğu gibi y harfi ile değiştirecektir.
İlgili değiştirme işlemleri yapıldıktan sonra makinemiz ve bandın durumu aşağıdaki şekilde olacaktır:
Görüldüğü üzere makine, q0 durumuna geri gelmiş ve bant ilk gördüğü x harfi için bir sağa sarılmıştır.
q0 durumunda, daha fazla a harfi kalmadığı için q3 durumuna geçiyoruz. Bu duruma geçme koşulumuz y bulunması hali.
q3 durumunda ise, bandın sonuna kadar y okudukça ilerliyoruz. Buradaki kritik nokta, şayet a ve b harflerinin sayısı eşitse, boşluk sembolüne kadar ilerleyeceğimizdir. Şayet b harfleri, a harflerinden fazla olursa q3 durumunda kalırız çünkü henüz hala y ile değiştirilmeyen b harfleri olacak ve makine q3 durumunda kalacaktır.
Şayet a harfinin sayısı b’den fazla olursa, bu durumda q1’de kalacağız. Çünkü bir a harfi x ile değiştikten sonra bir de b harfinin y ile değişmesi gerekecek. Bunu yapabileceğimiz bir b harfi bulunmayacak çünkü bütün b’ler zaten y ile değişmiş olacak ve makinemiz bu durumu kabul etmeyecek.
Turing makineleri ile ilgili daha detaylı bilgi için aşağıdaki bağlantıya tıklayabilirsiniz:
http://www.bilgisayarkavramlari.com/2009/06/27/turing-makinesi-turing-machine/
çok teşekkür ederim ayrıntılı olarak anlatmışınız allah razı olsun
Allah razı olsun çok güzel anlatmışsınız..
Çok güzel anlatmış ve açıklamışsınız. Ancak direkt cevabı yani diagramı çizmişsiniz. Benim sorum şu olacak bu diagramı nasıl çiziyoruz. Basit bir yöntemi vs. var mı ? Bir table’a çevirmek sonra diagramı çizmek vs. gibi bir şey var mı ? Yani siz sorunun cevabı olan diagramı direkt vermiş ve bir bakıma sağlamasını yapmışsınız. Ancak sınavda bizden diagram çizmemiz isteniyor. Bu diagram’ı nasıl çiziyoruz , aşamaları vs. var mı? Bunu da açıklarsanız çok sevinirim.Teşekkürler
selamlar,
örnek baya yararlı. peki bir kelime ve devamında kelimenin tersi gelen bir kelimeyi kabul eden bir turing makinesini tasarlarken nasıl düşünmeliyiz? örnek vermek gerekirse abbbba kelimesini kabul eder fakat abbba kelmesini kabul etmeyen bir makina.
Böyle bir soruda öncelikle bir strateji belirlemek gerekiyor. Problem, tek boyutlu bir bant üzerinde sadece ileri geri sarıp okuma ve yazma yaparak bu kontrolü nasıl gerçekleştireceğimiz.
Öncelikle belirtmeliyim ki bu ve benzeri soruların birden fazla çözümü olabilir. Örneğin kelimenin orta noktasını bulup çözüme başlayan çeşitli çözüm yolları okumuştum ancak ben aşağıdaki gibi bir çözümü önerebilirim.
Öncelikle problem oldukça meşhur bir palindrome (aks-i müfrettir). Bu tip sorularda kullanılacak yöntemlerden birisi kelimenin başından ve sonundan harf eksiltmek yönündedir.
Çözümü bir örnek üzerinden açıklamaya çalışayım. Sizin verdiğiniz örneği ele alalım “abbba” kelimesinin tam başında okuyucumuzun (kafa, head) olduğunu kabul edelim. Bu yazıda kafanın konumunu iki || sembolü ile göstereceğim:
*|a|bbba* –> buradaki * sembolleri boşluğu sembolize ediyor.
Şimdi ilk yapacağımız işlem kafanın üzerinde olduğu harfi okumak ve aynı harfi kelimenin sonundan silmek.
okunan harf : a , silinecek harf a
**bbba|*| : boşluk görene kadar sağa sardık.
**bb|a|* : bir geri sardık
**bb|*|* : a harfi bulunduğu için sildik
*|*|bb** : boşluk görene kadar tekrar başa sarıyoruz (burada optimizasyon için sondan silerek de başlanabilir
**|b|b** : okunan harf b o halde sondan silinecek harf b olmalı
***b|*|* : boşluk görene kadar sona sarıyoruz.
***|b|** : bir geri sarıyoruz ve b harfini arıyoruz
***|*|** : b harfi görüldüğü için siliyoruz ve bant boş olduğu için (boşluk dışında harf olmadığı için) işlemi bitirerek kelimenin palindrome (aksi müfret) olduğunu kabul ediyoruz.
Sanırım bunlara göre FSM çizmeniz artık oldukça basit olacaktır. Yine de sorun yaşarsanız mesaj yazın çizip yayınlamaya çalışırım.
Benzer bir konu push down automata başlığında geçiyor okuyabilirsiniz:
http://www.bilgisayarkavramlari.com/2009/09/15/push-down-automata/
Başarılar
anlatımınız için teşekkür ediyorum.Bir sorum olacaktı b’ler a’nın en az iki katı olması istenirse böyle bir durumda nasıl bir turing makinesi çizerim? Teşekkürler…
Her a için iki adet b silin, sonuçta bantta sadece b kalıyor veya boş oluyorsa şart sağlanmıştır.
teşekkürler
Merhabalar hocam Dogu Akdeniz Üniversitesi Bilgisayar Mühendisliği son sınıfta okumaktayım. Su soruyu çözemedim yardımcı olurmusunuz acaba..
L={ an b2n+1 n=>0} turing makinesini tasarlayın ve Tasarladgnz Turing makinesinin calsmasn anlk tarifler kullanarak abbb girdisi icin izleyiniz( yazı cıkmadıysa a üzeri n b üzeri 2n+1)
yardımcı olursanız çok sevinirim, Saygılarımla..
Merhaba hocam İzmir Üniversitesi 3 sınıf bilgisayar mühendisliği öğrencisiyim.Turing machine ile ilgili x>y büyükse 2x değilse 3y yazdırmam gerekiyor yardımcı olurmusunuz ?
Saygılarımla..
Hocam merhaba, çok güzel anlatmışsınız teşekkürler. Benim takıldığım nokta 3 e yada 5 e bölünüyorsa true bölünmüyorsa false gibi bir durumu nasıl yapmamız gerekiyor?
burada çizilen state diagramın yetersiz olduğunu düşünüyorum. eger a ların sayısı b lerden fazlaysa q1 state inden bir tane empty kol çıkması lazım.
öyle bir durumda q1 değil q2’de problem yaşanır ve dediğiniz gibi bir boşluk değerinin banttan okunması gerekir ki bu durumda makine için (sonlu durum makinesi (finite state machine) ) hata oluşacağından makine bu durumu kabul etmeyecektir. Yani problemin çözümü olan eşit sayıdaki a ve b koşulunun kontrolünü doğru yapacaktır.
hocam merhaba. boyutu çift ortasında 01 olan stringi turing makinesiyle nasıl çizebiliriz ?
sonunda * görene kadar devam eden, gördüğü 0 ları 1 e, 1 leri 0 lara çeviren ve başladığı yere geri dönen turing makinesi örneği nasıl olur?
Merhaba hocam peki 0^2n1^2n olan turing makinesinde nasıl bir çözüm yolu izleyebiliriz ?
Hocam elimizdeki Turing Makinesi’nin dilini a üzeri n / b üzeri n şeklinde nasıl bulabiliriz? Nasıl bir yol izlememiz gerek? Rastgele a ve b değerleri verip kontrol ederek mi doğru sonuca ulaşabiliriz yoksa bir yöntemi var mı?