∑={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, #>>>
Yazar Arşivleri: Ahmet Cevahir ÇINAR
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. Church-Turing tezi: Mekanik olarak yapılabilen her hesaplamayı yapabilecek bir Turing makinesi vardır. Church-Turing tezine göre,>>>
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 → X+X | X*X | X | a gramerini belirsiz midir değil midir? ‘a+a*a’ ifadesini türeterek>>>
C={0^n1^n|n>= 0} dilinin içerikten bağımsız gramerini (context-free grammar) yazınız? Dilimiz n=0 durumunda null üretir Dilimiz n=1 durumunda 01 üretir Dilimiz n=2 durumunda 0011 üretir Bu şekilde devam eder. Bağımsız grameri (context-free grammar): S->S1 S1->0S11|null
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ı sağlayamaması durumunda olmayana ergi(proof by contradiction) ile ispat ederiz. Pompalama Önsavı (Pumping Lemma) şartları: -A>>>
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)*
A dili düzenli (regular) ise B dili düzenli ise AUB’nin düzenli olduğunu ispatlayınız? İki düzenli dilin birleşimi düzenlidir. Bunu örnekle ispat edelim: Örneğin: RE1=a(aa)* RE2=(aa)* olsun. RE1’e ait dil: L1={a,aaa,aaaaa,…} – 1,3,5,7,9 şeklinde tek sayıda a ifadelerinin olduğu bir dil RE2’ye ait dil: L2={null,aa,aaaa,aaaaaa,…} – Boş,2,4,6,8 şeklinde çift sayıda a ifadelerinin olduğu bir dil L1UL2={null,>>>
Hesaplanabilirlik (Computability) ve Karmaşıklık (Complexity) kavramlarını tanımlayınız? Hesaplanabilirlik (Computability), bir problemin hesaplanıp hesaplanamayacağını yani bir çözümünün olup olmadığını belirtir. Bir problem belli prensiplerle bir hesaplama cihazı ile çözülebiliyorsa hesaplanabilirdir. Bu tip problemler hesaplanabilir(computable), çözülebilir(solvable), karar verilebilir(decidable) ve özyineli(recursive) olarak ta adlandırılmaktadır. 1930’lu yıllarda Gödel, Turing ve Church bazı problemlerin çözülemeyeceğini göstermiştir. Halting (Durma) problemi, Post>>>
Yukarıdan Aşağıya Ayrıştırma (Top Down Parser) ve Aşağıdan Yukarıya Ayrıştırma (Bottom Up Parser) Nasıl Yapılır? Bir CFG’ye ait bir ifadenin kurallardan türetilmesi ve Yukarıdan Aşağıya Ayrıştırma (Top Down Parser) ve Aşağıdan Yukarıya Ayrıştırma (Bottom Up Parser) teknikleriyle ağaç yapısında gösterimi anlatılmaktadır. S->aABe A->Abc|b B->d w=abbcde ifadesini soldan sağa oluşturalım: S->aABe S->aAbcBe S->abbcBe S->abbcde sağdan sola>>>
Context-Free Grammar (CFG) to Greibach Normal Form (GNF) GNF dönüşümü yapılmadan önce CFG’nin CNF’ye uygun olması gerekmektedir. Yani içerisinde null, unit ve gereksiz ifadeler olmamalıdır. GNF’nin temel prensibi kuralların bir terminal ile başlamasıdır. A->b A->bD1….Dn S->null şeklinde ifade edildiği zaman GNF’ye uymaktadır. Değişkenler yani non-terminaller, S’den başlayarak A1, A2, …, An şeklinde isimlendirilmelidir. Daha sonra>>>