Hesaplama Teorisi

Hesaplama Teorisi

Hesaplanabilirlik (Computability) ve Karmaşıklık (Complexity) kavramlarını tanımlayınız?

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…

Context-Free Grammar (CFG) to Greibach Normal Form (GNF)

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…

Context Free grammar (CFG) to Chomsky normal form (CNF) conversion

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ü…

How to remove Null Productions from CFG (Context-Free Grammar)?

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…

Moore makinesinin Mealy makinesine dönüştürülmesi

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:

Myhill–Nerode Teoremi

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…