Hesaplama Teorisi

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

İç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 –> )…

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ı

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

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

NP, NP-Complete, NP-Hard nedir?

NP, NP-Complete, NP-Hard nedir? Bir problem Evet veya Hayır şeklinde sonuç üretiyorsa buna karar problemi denir. P (Polynomial Time): Polinomsal zamanda çözülebilen karar problemlerinin karmaşıklık sınıfıdır. Yani polinomsal zamanda Evet veya Hayır şeklinde bir çözüm üretilir. NP (Non-deterministic-polynomial Time): Polinomsal…

İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?

İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız? İndirgeme bir problemi başka bir probleme dönüştürme işlemidir, böylece ikinci problemin çözümü birinci problemi çözmek için kullanılabilir. İndirgenebilirlik, A ve B gibi iki problemi içerir. Eğer A, B’ye indirgenebilirse, B’yi çözmek için…

Hesaplanabilir Fonksiyon (Computable Function) nedir?

Hesaplanabilir Fonksiyon (Computable Function) nedir? Bir f:Ʃ^*→Ʃ^* fonksiyonu, her bir w girdisinde, herhangi bir M Turing makinesi teybinde yalnızca f(w) ile sonlanırsa (halt) hesaplanabilir bir fonksiyondur. Basitçe bir fonksiyonun hesaplanabilir olması o fonksiyonun bir sonucunun çıkması anlamına gelir. Örneğin Church-Turing…