Muntazam Diller (Formal Languages)

Yazan : Şadi Evren ŞEKER

Kısaca istisnası olmayan dillere muntazam dil diyebiliriz.

Muntazam diller bilgisayar bilimlerinde, mantıkta ve dilbilim (linguistic) çalışmalarında kullanılan bir dil ailesidir. Dilde bulunan bütün öğeler ve dilin ulaşabileceği sınırlar belirli kurallar dahilinde tanımlanabiliyorsa bu dillere muntazam dil ismi verilir.

Bu anlamda bilgisayar bilimlerinde bulunan bütün programlama dillerini bu ailede düşünmek mümkündür.

Temel olarak bir dildeki harfleri bu harflerden oluşabilecek kelimelerin oluşma kurallarını (morphology) ve bu kelimelerin dizilimini (syntax) muntazam bir şekilde belirleyebilen kurallarımız varsa. Ve bu kuralların istisnası yoksa bu dilin bir muntazam dil olduğu söylenebilir.

Muntazam dilimizi tanımlamak için öncelikle dilin en ufak öğesi olan harflerden başlamak gerekir.

Alfabe ve Harf tanımı

Bir dilde kullanılan sembollerin her birisine harf denilir. Bu harflerin listesine alfabe (bazı kaynaklarda abece) denilir.

Örneğin haber mantığını (predicate logic) ele alacak olursak bu mantığın ifade ettiği dil için ∧, ¬, ∀ , ) , ( sembolleri kullanılır. Ayrıca mantığımızdaki değişkenleri ve önermeleri gösteren  x₀, x₁, x₂, … şeklinde sonsuz harf bulunmaktadır.

Kelime (word) tanımı

Bir alfabedeki sembollerin (harflerin) o dildeki kelimebilim(morphology) kurallarına uygun olarak oluşturduğu dizilime kelime ismi verilir. Kelimeler dildeki anlamlı en küçük birimlerdir ve tek başlarına sadece bir birimlik bilgi ifade ederler. Daha karmaşık bilgi ifadeleri için cümlelere ihtiyaç duyulur. Ne yazık ki dilbilimde bir kelimenin anlattığı bilgi ile bir cümlenin anlattığı bilgi arasında kesin bir çizgi bulunmamaktadır. Örneğin bazı doğal dillerde tek kelime ile anlatılan bir duygu veya olay, başka dillere bir kelime grubu hatta bazan bir cümle ile çevrilebilmektedir.

Muntazam diller için de aynı durum söz konusudur. Dilin tasarımında hangi bilginin yeterli varlık oluşturacağı ve ne kadar detaya inileceği kararlaştırılır.

Hatta bir dilin var olması için sözdizim (syntax) seviyesinin bulunması gerekmez. Yani sadece kelimeler olan ve kelimelerin dizilmesi gerekmeyen diller de bulunabilir.

Bir dilde üretilebilecek kelimelerin belirli kurallarla tanımlanması ve bu kuralların dışına çıkan istisna bulunmaması durumunda bu dile muntazam dil denilebilir.

Örneğin düzenli ifadeleri (regular expressions) ele alırsak, bu ifadelerin kullanılması ile dilde oluşabilecek sonsuz sayıdaki kelime belirlenebilir.

(a + b)* şeklindeki bir düzenli ifadeden a ve b harfleri kullanılarak (istenilen sıra ve istenilen sayıda) kleene yıldızı sayesinde boş kümeyi de kapsayan bütün kelimeler üretilebilir.

Muntazam Dil tanımı

Yukarıdaki dilin öğelerini tanımladıktan sonra dili tanımlamak mümkündür.

Σ sembolü ile dilimizdeki alfabeyi yani harfler kümesini gösterecek olursak L ile gösterilen dilimiz Σ^* ile üretilebilen kelimeler kümesidir.

Bu tanıma ilave olarak muntazam dil kavramının matematik ve bilgisayar bilimlerinde geçen pek çok “dil” kelimesini karşıladığını söyleyebiliriz. Yani aslında matematik ve bilgisayar bilimlerinde geçen “dil” kelimesi aslında tam olarak “muntazam dile” karşılık gelmektedir.

Örneğin içerikten bağımsız dil (context free language) terimi aslında içerikten bağımsız muntazam dil anlamında kullanılmaktadır. Benzer şekilde düzenli diller (regular languages) terimi aslında düzenli muntazam dil (regular formal languages) anlamında kullanılmaktadır. Dolayısıyla matematik ve bilgisayar bilimlerinin uğraştığı bütün dilleri ve kullandıkları bütün dilleri muntazam dil (formal language) olarak tanımlamak mümkündür. Bunun tek istisnası bilgisayar bilimlerindeki yapay zeka konusunun altında geçen doğal dil işleme konusudur.

Muntazam dil çalışmaları

Muntazam diller üzerinde yapılan çalışmalardan birincisi bir muntazam dilin nasıl tanımlanacağıdır. Bu alanda yapılan bazı çalışmalar sonucunda elde edilen yaklaşımları aşağıdaki şekilde sayabiliriz:

• Muntazam bir dilbilgisi (formal grammer) tarafından üretilen dillere Muntazam dil (formal language) ismi verilir. Bu tanım Chomsky Hiyerarşisi tarafından sınıflandırılan dilbilgileri ile gösterilebilir.
• Düzenli ifadelerin (Regular expressions) bir örneği ile üretilebilen dillere muntazam dil ismi verilir.
• Bir otomat tarafından üretilen (sonlu durum otomatı (finite state automat) veya Turing Makinesi (Turing Machine) gibi) dillere muntazam dil ismi verilir.

Yukarıdaki bu tanımlama çalışmalarının yanında muntazam diller ile ilgili aşağıdaki sorulara da cevap aranmaktadır.

• Tanımlama yeteneği. Bir dilin tanımlayabilme gücü ve tanımlayabildiği dilin büyüklüğü nedir? Aynı güce ve yeteneğe sahip ikinci bir dil farklı bir şekilde olabilir  mi? Bütün dilleri gösteren bir dil yapılabilir mi? şeklindeki soruları bu grup altında toplayabiliriz.
• Algılama yeteneği. Verilen bir kelimenin verilen bir dile ait olup olmadığının algılanması yeteneğidir. Elimizde muntazam bir dilbilgisi (grammer) olduğunu kabul edelim. Bu dilden olan veya olmayan bir kelime verildiğinde bu kelimenin analiz edilmesi ve dile ait olup olmadığının algılanması en verimli nasıl yapılabilir? sorusuna cevap arayan çalışmalardır.
• Karşılaştırma yeteneği. Elimizde iki dil bulunsun. Bu iki dilin birbirine göre farklarının algılanılması, bir dilde olup diğer dilde olmayan veya iki dilde ortak olan kelime ve cümlelerin tespiti gibi konularda çalışılan çalışma grubudur.

Yukarıdaki bu problemler genel olarak algoritma analizi (analysis of algorithms) altındaki karmaşıklık teorisi (complexity theory) alanın çalışma konularına girmektedir.

Diller üzerinde tanımlı işlemler

Diller üzerinde de farklı işlemlerin yapılması mümkündür. Aşağıda bu işlemler ve tanımları verilmiştir:

Dillerin kesişimi (intersection): Temel olarak bir dili o dildeki kurallar ve alfabe marifetiyle üretilebilecek kelimeler kümesi olarak tanımlarsak, iki dilin kesişimi aslında iki dilde üretilebilecek kelimelerin kesişimi olmuş olur.L₁ ∩ L₂ şeklinde gösterilir.

Üleştirme işlemi (concetanation): İki dilden üleştirme yapmak için birinci dilden bir kelime ile ikinci dilden bir kelimenin arka arkaya eklenmesi ile yeni bir kelime oluşturulması kastedilir. Yani L₁ dilinden k kelimesi ile L₂ dilinden l kelimesi alınıp kl veya lk şeklinde kelime üretme işlemidir. L₁L₂ şeklinde gösterilir.

Tümleyen işlemi (Complement): Bir dildeki güç kümesinden (power set) o dildeki dilbilgisine (grammer) göre çıkarılabilen kelimelerin farkıdır. Yani alfabede olan harflerle yazılabilecek bütün kelimelerin, dilde izin verilen kelimelerle fark kümesidir. ¬L şeklinde veya L şeklinde gösterilir.

Kleene Yıldızı (Kleene Star): Bir dildeki alfabe üzerinde boş küme dahil olmak üzere üretilebilecek bütün kelimeler kümesidir. Bir anlamda güç kümesi (power set) ismi de verilebilir. Kullanımı aslında düzenli ifadelerden (regular expressions) alınmıştır.

Ters işlemi (reverse): Bir dildeki herhangi bir kelimenin yazılışının terse çevrilmiş halidir. Örneğin “abc”‘nin tersi “cba” şeklindedir. Daha akademik olarak iki kuralla tanımlanabilir.

• Şayet dilimizdeki boş kelimeyi e sembolü ile gösterirsek e^R = e olur yani boş kelimenin tersi yine boş kelimedir.
• Boş kelime dışındaki herhangi bir kelime için  w = x₁…x_n şeklinde n adet harf ile yazıldığını düşünelim, bu durumda tersi  w^R = x_n…x₁, olur

Bu durumda muntazam bir dil  L için , L^R = {w^R | w ∈ L} olarak tanım yapılabilir.