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:

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.

Yorumlar

  1. Mahmut

    Hocam sınavda şöyle bir soru çıkmıştı karşımıza :

    Pozitif Rasyonel sayıların tamamını ekrana yazan bir program hazırlandığını
    düşünün. Programın çıktıları sayılabilir (enumerable) bir dili tanımlar mı? İspatlayınız.

    bunun cevabı nedir ?

Mahmut için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir