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= {aⁿbⁿ , 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:

δ(q₀,a,z) = (q₀,a)
δ(q₀,a,a) = (q₀,a)
δ(q₀,b,a) = (q₁,x)
δ(q₁,b,a) = (q₁,x)
δ(q₁,b,z) = (q_f,z)

δ(state₁,read,pop) = (state₂,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= {aⁿbⁿ , 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.

372 views