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
Aylık Arşivler: Haziran 2017
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>>>
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: