:::: MENU ::::
Hesaplama Teorisi

A dili düzenli (regular) ise B dili düzenli ise AUB’nin düzenli olduğunu ispatlayınız?

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, a,aa,aaa,aaaa,aaaaa,aaaaaa,…} – Boş, 1,2,3,4,5,6 şeklinde a ifadelerinin bulunduğu bir bil oluşur.
Bu dil RE(L1UL2)=a* ile ifade edilebildiğinden düzenlidir.

Aybüke BABADAĞ’ın cevabı:

aybuke-babadag-duzenli-dillerin-birlesimi


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 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 Correspondence problemi çözülemeyen/karar verilemeyen(undecidable) problemlerdendir.

Karmaşıklık (Complexity), bir probleminin çözümünün ne kadar zaman (adım) veya alan (bellek) ile gerçekleştirildiğini belirlemek için kullanılır. Bu aşamaya geçilebilmesi için problemin hesaplanabilir olması gerekmektedir. En iyi algoritma en hızlı ve en az hafıza ihtiyacı ile çalışan algoritmadır.


Yukarıdan Aşağıya Ayrıştırma (Top Down Parser) ve Aşağıdan Yukarıya Ayrıştırma (Bottom Up Parser)

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 oluşturalım:

S->aABe
S->aAde
S->aAbcde
S->abbcde

Ağaca yerleşimi de videodan izleyebilirsiniz:


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 GNF’ye uymaktadır.

Değişkenler yani non-terminaller, S’den başlayarak A1, A2, …, An şeklinde isimlendirilmelidir.
Daha sonra kurallar uygulanarak, şartlar sağlanıncaya kadar yer değiştirmeler yapılır.

Kurallar ve Örnek:
CFG-GNF

Videolu Anlatım:


Sayfalar:12345678