:::: MENU ::::
Hesaplama Teorisi

İçerikten bağımsız bir gramerin (context-free grammar) üretebileceği ifadeler nelerdir?

Aşağıda içerikten bağımsız bir gramer (context-free grammar) verilmiştir. Başlangıç değişkeni exp ile gösterilmiştir. Bu gramer hangi ifadeleri üretebilir?

exp –> INT
exp –> exp OP exp
exp –> LP exp RP
OP –> +|-|*|/
LP –> (
RP –> )
INT –> 0|1|2|3|4|5|6|7|8|9

Cevap:

exp->INT’e göre 0-9 arasındaki sayılar tek tek üretilebilir.

exp->exp OP exp’e göre 0+0, 0-0,0*0,0/0 yani tüm INT ile gösterilen sayılar ve verilen operantlar olabilir.

exp->LP exp RP’ye göre de (parantez içinde tek tek tüm INT ile gösterilen sayılar) ve yine parantez içinde bir önceki durumda olabileceğini belirttiğim ifadeler olabilir.

Not: Soruyu bir Youtube videosunun yorumunda gördüm, kendimce cevap verdim, umarım doğrudur.


Düzenli bir ifadenin NFA ve DFA’sını çizen çevrimiçi bir web sayfası

Düzenli bir ifadenin NFA ve DFA’sını çizen çevrimiçi bir web sayfası:

http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

Thompson-McNaughton-Yamada temelli NFA ve bu NFA’nın DFA’sını çizerek bizlere sunuyor.

Örneğin a*(b|a)* ifadesinin NFA’sı:

Aynı ifadenin DFA’sı:

HackingOff sitesinde başka faydalı içerikler de bulunuyor. İncelemekte fayda var.


Hesaplama Teorisi ile ilgili temel sorular ve cevapları

Hesaplama Teorisi ile ilgili temel sorular ve cevapları:

Not: Kendime not niteliğinde olduğundan eksikler ve yanlışlar olabilir. Görürseniz uyarınız böylece ben de yanlışımı düzeltmiş olurum. Farklı fikirler, ifadeler ve örnekler ile yorum yazarak cevapları zenginleştirebilirsiniz.

1-Hesaplanabilirlik (Computability) ve Karmaşıklık (Complexity) kavramlarını tanımlayınız?
2-A dili düzenli (regular) ise B dili düzenli ise AUB’nin düzenli olduğunu ispatlayınız?
3-Aşağıdaki otomatın düzenli ifadesini(regular expression) yazınız?
DFA
4-C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi?
5-C={0n1n|n>= 0} dilinin içerikten bağımsız gramerini (context-free grammar) yazınız?
6-Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?
7- Church-Turing tezi nedir? Açıklayınız?
8-∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinasını tanımlayınız?
9-Bir Turing makinasının biçimsel (formal) tanımını yapınız?
10-Halting problemi nedir?
11- Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz?
12-Karar Verilebilirlik (Decidability) nedir?
13-Algoritma nedir?
14-Hesaplanabilir Fonksiyon (Computable Function) nedir?
15-İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?
16-Özyineleme (Recursion) teoremi nedir?
17-3-SAT problemini Clique problemine indirgeyiniz?
18-NP, NP-Complete, NP-Hard nedir?
19-İnatçılık (intractability) nedir?


İnatçılık (intractability) nedir?

İnatçılık (intractability) nedir?

İlkesel olarak çözülebilen bazı hesaplama problemlerinin uygulamada(gerçek hayatta) kullanılamayacak kadar çok zaman ve bellek gerektirmesi durumunda bu tür problemlere inatçı (intractable) denir.

SAT problemi ve diğer NP-complete problemlerin intractable olduğu düşünülmektedir fakat ispatlanmamıştır.

Verimli (efficient) bir zamanda çözülebilen problemlere tractable, çözülemeyenlere intractable denmektedir.

Verimli (efficient) zamanlar: O(n) O(n log n) O(n^3 log^2 n)
Verimsiz (inefficient) zamanlar: O(2^n) O(n!)


Sayfalar:12345678