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 olmasının ve önemli olmasının sebebi bir düzenli ifade (regular expression) ile yazılmasının imkansız oluşu ancak içerikten bağımsız dil ile yazılmasının mümkün olmasındandır.

Şimdi bu dilin aşağı sürüklemeli otomatını aşağıdaki şekilde çıkaraibiliyoruz:

δ(q0,a,z) = (q0,a)
δ(q0,a,a) = (q0,a)
δ(q0,b,a) = (q1,x)
δ(q1,b,a) = (q1,x)
δ(q1,b,z) = (qf,z)

δ(state1,read,pop) = (state2,push)

Yukarıdaki PDA (push down automaton) tasarıımnda dikkat edilirse iki durum (state) arasındaki geçişler ile yukarıdaki dili tasarlamak mümkündür. Bu sayede bu dilin bir içerik bağımsız dil olduğu söylenebilir.

Ayrıca yukarıdaki tanımda kullandığımız ” içerik bağımsız bir grammer ile oluşturulması durumu” ifadesini de açıklayarak buna da bir örnek verelim ve dilimizin ( L= {anbn , n>0} ) CFG (context free grammer, içerik bağımsız gramer)  karşılığını aşağıda yazalım:

S -> aSb | ab

Yukarıdaki yazılışta, dilin sonucu ab veya aSb olarak çıkacaktır ancak S devamlısı (nonterminal) bitmek için bir sonuncuya (terminal) ihtiyaç duyacaktır bu değer de yine ab olacaktır.

Sonuçta yukarıdaki gramer ile istenilen uzunlukta sırasıyla a ve b lerden oluşsan dil tasarlanabilir ve üretilen bütün dillerde a’nın sayısı ile b’nin sayısı eşittir.

Yorumlar

  1. erdo

    hocam merhaba;
    bu döküman çok güzel olmuş ama başka bir başlık altında detaylı örneklerle gramer, dil nasıl ve neye göre oluşturulur açıklayabilirseniz sevinirim.
    iyi çalışmalar.

  2. Şadi Evren ŞEKER Article Author

    Gramer ve dil oluşturulmasının CFL ile bir ilgisi yok. Yani CFL gösterimi bir gösterimdir ve sizin göstermek istediğiniz dili göstermek için kullanılır. Bu gösterimin dil çıkarımı ile bir ilgisi yoktur.

    Diğer bir deyişle sizin bir diliniz vardır ve siz bu dili herhangi bir gösterim yöntemi ile (RE, DFA, NFA, CFG, Turing Machine, PDA vs. ) gösterirsiniz.

    Sizin bahsettiğiniz konu ile ilgili durum genelde bir dilin metin olarak tanımı yapılıp karşılığında bir gösterimle ifadesi şeklinde sorulabilir.
    Örneğin CFG ile sonunda her zaman a harfi olan ve {a,b} kümesindeki bütün harfleri gösterebilen dil gösterimi sorulursa, aşağıdaki şekilde bir çözüm üretilebilir:
    S->Xa
    X->aX|bX|.

    Yukarıdaki dilde, X ifadesi tek başına ele alınırsa zaten a ve b ile üretilebilecek bütün kelimeleri gösterir (buradaki nokta sembolü lambda veya epsilon ile gösterilen boş sembol anlamındadır).
    İlave olarak başlangıç seviyesinde, sonunda a bulunma şartı eklenmiştir.

    Doğal dilde verilen ve dilin tanımının yapıldığı metinden CFG gösterimine çevirim ise tam başarıyla olmamakla birlikte belirli bir başarıyla sağlanabilmektedir. Bu konuyla doğal dil işleme çalışmaları ilgilenir ve aşağıda örnek bir tez dokümanı bulunmaktadır:

    http://www.shedai.net/~tuja/

    Başarılar

Bir cevap yazın

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