Yazan : Şadi Evren ŞEKER Knuth-Morris-Prat algoritması bir kelimenin (yada bir metin parçasının) bir metin içerisinde aranmasını sağlayan algoritmadır. Basitçe bu algoritmada bir kelimenin aranan metinde bakılması ve bakıldığı yerde bulunamaması durumunda nerede olabileceği ile ilgili bir bilginin elde edilmesi hedeflenir. Algoritma aranan kelimenin, aranan metinde bulunmaması durumunda, kelimenin içerisindeki harflerden yola çıkarak birden fazla […]
Category: Automata (otomatlar, özdevinirler)
Özdevinimliler, Özdevinirler veya otomatlar olarak türkçede geçen ve ingilizce literatüründe automata olan konu başlığı için ayrılmış kategöridir.
Atomluluk (Atomicity)
Yazan: Şadi Evren ŞEKER Latince bölünemez anlamına gelen atom kökünden üretilen bu kelime, bilgisayar bilimlerinde çeşitli alanlarda bir bilginin veya bir varlığın bölünemediğini ifade eder. Örneğin programlama dillerinde bir dilin atomic (bölünemez) en küçük üyesi bu anlama gelmektedir. Mesela C dilinde her satır (statement) atomic (bölünemez) bir varlıktır. Benzer şekilde bir verinin bölünemezliğini ifade etmek […]
Tehlike (Hazard)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özellikle de mantıksal devre tasarımı sırasında karşılaşılan bir durumdur. Basitçe sistemde oluşan veya oluşabilecek tehlikeleri ifade eder. Yani örneğin sistemdeki kapıların (ve, veya, yahut kapıları) yanlış çalışması sonucunda oluşan tehlikelerdir. Temel olarak 3 ayrı grupta toplamak mümkündür: Sabit Tehlikeler (Static Hazards) Müteharrik Tehlikeler (Dinamik Tehlikeler, Dynamic Hazards) Fonksiyonel […]
İçerik Bağımsız Gramerler için Pompalama Önsavı (Pumping Lemma for Context Free Grammers)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir dilin, içerik bağımsız gramer (context free grammer, CFG) ile gösterilemeyeceğini ispatlamaya yarar. Yani pompalama ön savı sayesinde bir dilin CFG olmadığı ispatlanabilir ancak olduğu ispatlanamaz. Şayet pompalama önsavını geçemyorsa CFG değildir denilebilir ancak geçmesi olmasını gerektirmez. Pomplama önsavı (pumping lemma) kısaca bir dili aşağıdaki gramere uydurmaya çalışır: […]
Düzenli İfadelerde Pompalama Önsavı (Pumping Lemma for Regular Expressions)
Yazan : Şadi Evren ŞEKER Bir dilin Düzenli ifadele (Regular expression) olup olmadığının belirlenmesi için kullanılan pomplama önsavıdı (pumping lemma). Basitçe düzenli ifadede olup olmadığı sınanacak bir w dili için (yani L = w için) w= xyz şeklinde bir açılım sınanır. Buradaki sınama sırasında aşağıdaki koşulların sağlanması beklenir: |y| ≥ 1 |xy| ≤ p bütün […]
Pompalama Önsavı (Pumping Lemma)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde dil tasarımı (language design, compiler design) konusunda önemli araçlardan birisidir. Bu önsava (lemma) göre şayet bir dil, bir herhangi bir gruba ( içerik bağımsız dil (context free language) veya düzenli ifadeler (Regular expression) yada farklı bir dil grubu ) dahil olarak kabul ediliyorsa, bu dil ne kadar pompalanırsa […]
İçerikten Bağımsız Gramer (context free grammer, CFG)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde, dil tasarımı sırasında kullanılan bir gramer tipidir. Basitçe bir dilin kurallarını (dilbilgisini, grammer) tanımlamak için kullanılır. Örneğin: S -> a Yukarıdaki dil tanımında bir büyük harfle gösterilen (S) bir de küçük harfle gösterilen (a) sembolleri bulunmaktadır. Bu satır, S devamlısının(nonterminal) a sonuncusuna(terminal) dönüştüğünü göstermektedir. Kısaca dildeki kuralları ifade […]
İçerikten bağımsız dil (Context Free Language, CFL)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir dilin tasarımı sırasında, içerik bağımsız bir gramer ile oluşturulması durumudur. Basitçe bir aşağı sürüklemeli otomat (push down automata) tarafından kabul edilen dil çeşididir. Bazı kaynaklarda bağlamdan bağımsız dil olarak da geçmektedir. Örneğin çok meşhur L= {anbn , n>0} dilini ele alalım. Bu dil örneğinin bu kadar meşhur […]
EBNF (Uzatılmış BNF, Extended Backus Normal Form)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde dil tasarımı konusunda kullanılan backus normal şeklinin (backus normal form) özel bir halidir. Basitçe standart BNF’te yazılan kuralların birleştirilerek daha sade yazılmasını hedefler. Bu durumu aşağıdaki örnek üzerinden görebiliriz: Örneğin BNF olarak yazılan dilimize göre: <EGER> ::= if( <KOSUL>) | if( <KOSUL>) else şeklinde bir satırımız bulunsun. Bu […]
YACC
Yazan : Şadi Evren ŞEKER YACC, bilgisayara bilimlerinin önemli dallarından birisi olan dil tasarımı ve dil geliştirilmesi sırasında (compiler teory) sıkça kullanılan bir kod üretici programdır. YACC basitçe dildeki sözdizim (syntax) tasarımı için kullanılır ve tasarladığımız dildeki kelimelerin sıralamasının istediğimiz şekilde girilip girilmediğini kontrol eder. Aynı zamanda sıralamadaki her kelimenin anlamını da yacc marifetiyle belirleyebiliriz. […]