Hesaplama Teorisi

Hesaplama Teorisi

Karar Verilebilirlik (Decidability) nedir?

Karar Verilebilirlik (Decidability) nedir? Bir dil Turing makinesi tarafından kabul ediliyorsa rekürsif/özyineli veya karar verilebilir (decidable) olarak adlandırılır. Bütün karar verilebilir diller Turing Acceptable’dır. Diller: -Karar Verilebilir (Decidable) -Turing Kabul Eder (Turing Acceptable) -Turing Kabul Etmez (Non-Turing Acceptable) olarak sınıflandırılabilir….

Durma (Halting) problemi nedir?

Durma (Halting) problemi nedir? Bir programın belli bir zaman sonra durup durmayacağı belirsizdir. D(P,G) şeklinde bir durup durmamayı bilen program yazıldığını düşünelim. Burada P programı G girdisi ile çalıştığı zaman durup durmayacağını D(P,G) programımız söyleyecek olsun. D(P,G)’nin bir sonuç döndüreceğini…

Bir Turing makinasının biçimsel (formal) tanımını yapınız?

Bir Turing makinasının biçimsel (formal) tanımını yapınız? Tip-0 gramerleri tarafından üretilen rekürsif numaralandırılabilir dili tanımlayan makinalara Turing makinesi denir. 1936 yılında Alan Turing tarafından tasarlanmıştır. Turing makinası girdiyi sonsuz hücreli bir teyp üzerindeymiş gibi modelleyen matematiksel bir yaklaşımdır. Teypten verileri…

Church-Turing tezi nedir? Açıklayınız?

Church-Turing tezi nedir? Açıklayınız? Alonzo Church tarafından ortaya atılan teze göre, herhangi bir algoritma, herhangi bir donanımda çalışabiliyorsa, bu donanıma karşılık gelen bir Turing makinesi olduğudur. Daha basit bir ifadeyle, Turing makineleri, herhangi bir donanımın yaptığı algoritmasal işlemleri yerine getirebilir….

Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?

Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız? Bir L(G) içerikten bağımsız gramerinden (context-free grammar) üretilmiş w ifadesi için birden fazla türetme ağacı (derivation tree) oluşturulabiliyorsa bu tip gramere belirsiz(ambigious) denir ve bu durumun oluşmasına Belirsizlik (Ambiguity) ismi verilir. Örneğin: X →…

C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi?

C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi? Bir dilin düzenli olup olmadığını anlamak için pompalama önsavı(pumping lemma) şartlarını sağlaması gerekmektedir. Bir dilin düzenli olmadığını en başta o dili düzenli kabul ederek pompalama önsavı(pumping lemma) şartlarını…

Bir otomatın düzenli ifadesini (regular expression) yazınız?

Aşağıdaki otomatın düzenli ifadesini(regular expression) yazınız? Çözüm: Arden Teoremi ile çözmeye çalışalım: Not: Henüz çözemedim q1=q2a+q3b+null q2=q1a+q2b+q3a q3=q1b oluşturulur. q2=q1a+q2b+q3a q2=q1a+q2b+(q1b)a q2=q1(a+ba)+q2b q2=q1(a+ba)+b* q1=q2a+q3b+null q1=(q1(a+ba)+b*)a+(q1b)b+null q1=q1((a+ba)+b*))a+bb)+null q1=q1((a+ba)+b*))a+bb)+null q1=null((a+ba)+b*))a+bb)* q1=((a+ba)+b*))a+bb)*