Özyineli Sayılabilir Diller (Recursively Enumerable Languages)

Yazan : Şadi Evren ŞEKER

Muntazam dillerden (formal languages) birisi olan ve bu özelliği ile Mantık, Matematik ve Bilgisayar bilimlerinin çalışma alanına giren bir dil çeşididir. Sınıflandırma olarak Chomsky Hiyerarşisinde (Chomsky Hierarchy) 0. seviye olan (Type 0) bu dile uygun bütün diller birer düzenli ifade (regular expression) ile gösterilebilir.

Muntazam dil (formal language) olması dolayısıyla dilde üretilen her özyineli sayılabilir kelime kümesi (recursively enumerable set) bütün kelimelerden çıkarılabilecek güç kümesinin (power set) bir alt kümesi olmak zorundadır. Bu anlamda bir özyineli sayılabilir dili aşağıdaki üç farklı tanımla tanımlamak mümkündür:

Bir dilde bulunan alfabeden üretilebilen bütük kelimeleri kabul eden dil yani Σ sembolü ile dilimizdeki alfabeyi yani harfler kümesini gösterecek olursak L ile gösterilen dilimiz Σ^* ile üretilebilen kelimeler kümesidir.

Turing makinesi (Turing machine) ile işlenebilen veya hesaplanabilir bir fonksiyon (computable function) bulunabilen dildir. Burada dikkat edilecek nokta dilin sonsuz olabileceğidir. Yani dilimizde sonsuz sayıda tekrar bulunabilir. Turing makinesi ve hesaplanabilirlik teorisi (computability theory) dikkatle okunacak olursa dilin sonsuz olmasının bir sakıncası yoktur. Teorik olarak sonlu zamanda bitiyor olması yeterlidir ve dil sonsuz bile olsa sonlu zamanda işleyen bir makine veya fonksiyon bulunabilir.

Şayt bir dilde üretilen bir dizgi (string) için bir Turing makinesi (turing machine) veya hesaplanabilir bir fonksiyon (computable function) bulunuyorsa, diğer bir ifadeyle ürettiğimiz turing makinesi şu üç durumdan birisini yapıyorsa:

bitmek (halt)
döngü (loop)
red etmek (reject)

bu durumda bu dil özyineli sayılabilir dildir denilebilir.

Özyineli sayılabilir diller temel olarak chomsky hiyerarşisinde (chomsky hierarchy) bulunan bütün diğer dilleri kapsar. Bu anlamda hiyerarşinin en alt seviye dilidir ve diğer dillere göre çok daha esnektir.

« Chomsky Hiyerarşisi ( Chomsky Hierarchy ) | Turing Makinesi (Turing Machine) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Özyineli Sayılabilir Diller (Recursively Enumerable Languages)' isimli yazı 27 Jun 2009 tarihinde, saat: 15:33 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 468 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), Bilgisayar Kavramları, Derleyiciler, Doğal Dil İşleme (NLP), Programlama Dilleri kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar