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)*
Kategori Arşivleri: Hesaplama Teorisi
Hesaplama Teorisi
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>>>
CFG’ler CNF’ye dönüştürülebilmektedir. Bir CFG’nin CNF’ye uygun olabilmesi için A->a A->BC S->e(epsilon) şeklinde ifade edilebilmesi gerekmektedir. Buradan çıkarılabilecek kurallar: -null/e(epsilon) ifadeler olmayacak -Bire bir A->B, B->C, C->D gibi nonterminal geçişleri olmayacak -terminal ve non-terminal semboller yan yana olmayacak -Üç sembollü herhangi bir ifade olmayacak. Yani A->BCD gibi. 1.Örnek: 2.Örnek:
How to remove Null Productions from CFG (Context-Free Grammar)? 1.Örnek: 2.Örnek: Null ifadeye giden terminal olmayan sembolleri tespit ettikten sonra sırasıyla ilgili nonterminal semboller yerine NULL değerini koyarak oluşabilecek alternatif ürünleri yazarız. Bu işlemin sonucunda ortada herhangi bir NULL değeri kalmaz.
Sonlu durum makinelerinin iki farklı gösterim biçimi olan Moore ve Mealy makinelerinin birbirine dönüşümü nasıl yapılır? Aşağıdaki videolarda Moore makinesi Mealy makinesine dönüştürülmüş… 1.Örnek: 2.Örnek:
Pumping Lemma for Regular Languages
Myhill–Nerode Teoremi, 1958 yılında Chicago üniversitesi akademisyenleri John Myhill ve Anil Nerode tarafından ortaya konmuş bir teoremdir. Myhill–Nerode Teoremi, bir dilin düzenli olduğunu ispatlamak için gerekli ve yeterli bir yaklaşımdır. Ayrıca bir DFA’nın minimal hale getirilmesinde de kullanılmaktadır. Myhill–Nerode Teoremi ile ilgili çalışmalarım sırasında aldığım notlar: