Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin özellikle dil alanında yapılan çalışmalarında muntazam dilleri (formal languages) tasnif etmek için kullanılan bir yapıdır. Literatürde Chomsky–Schützenberger hiyerarşisi olarak da geçmektedir.

Bilindiği üzere ( muntazam diller (formal langauges) veya CFG yazısından da okunabileceği üzere) muntazam dillerin dört özelliği bulunur. Bunlar özellikle içerikten bağımsız dillerin (context free languages) da temelini oluşturmuştur.

  • sonlular (terminals)
  • devamlılar (nonterminals)
  • üretim kuralları ( devamlıların değerlerini belirleyen geçiş kuralları)
  • Başlangıç devamlısı

Örneğin aşağıdaki içerikten bağımsız dilbilgisini (context free grammer) ele alalım

S → AB

A → Aa | ε

B → b

Yukarıdaki bu CFG tanımındaki sonlular (terminals) {a,b,ε } ,  devamlılar (nonterminals) { S,A,B } olarak tanımlanır. üretim kuralı olarak (production rules) S,A,B’nin açılımlarını gösteren ve → sembolü ile belirtilen satırlar bulunmaktadır. Son olarak başlangıç devamlısı (nonterminal) değeri olarak S kabul edilmiştir. Başlangıç devamlısı böyle bir kural bulunmamasına karşılık genelde S harfi (start kelimesinden gelmektedir) ile gösterilmekte ve ilk satırda bulunmaktadır.

Yukarıdaki bu CFG şayet düzenli ifadeye (regular expression) çevrilirse a*b şeklinde yazılabilir. Aslında burada anlatılan değer anb şeklinde de gösterilebilen istenildiği kadar a değeri alan (hiç almaya da bilir) ve sonra mutlaka b ile biten dildir.

Chomsky yukarıdaki şekilde tanımlanan muntazam diller (formal languages) için bir sınıflandırmaya gitmiş ve 4 seviye belirlemiştir.

şeklinde 4 seviye isimlendirilmiştir.Bu seviyelerde iler gidildikçe (seviye arttıkça) dili bağlayan kurallarda sıkılaşmakta ve dil daha kolay işlenebilir ve daha belirgin (deterministic) bir hal almaktadır.

Tip-0 dilleri bastiçe turing makinesi (turing machine) tarafından çalıştırılabilen ve bir şekilde bitecek olan dillerdir (hesaplanabilir diller (computable languages). Örneğin özyineli sayılabilir diller (recusive enumerable languages) bu seviyeden kabul edilir.

Tip-1 dilleri için içerk duyarlı diller örnek gösterilebilir. Basitçe αAβ → αγβ şeklindeki gösterime sahip bir dildir. Buradaki A devamlı (nonterminal) ve α,γ,β birer sonlu (terminal) terimdir. Bu sonlulardan α ve β boş harf (yani ε veya bazı kaynaklarda λ) olabilir ancak γ mutlak bir değere sahip olmalıdır (yani boş olamaz) Ayrıca bu tipte

S → ε

şeklinde bir kurala da izin verilmektedir. Burada S devamlısının sağ tarafta olmaması gerekmektedir. Bu diller doğrusal bağlı otomatlar (linear bounded automaton) ile gösterilebilir. Doğrusal bağlı otomatlar, turing makinelerinin özel bir halidir ve Turing makinesinde bulunan bantın sabit uzunlukta olduğu (çalışmanın sabit zaman sonra sona ereceği) kabul edilir.

Tip-2  diller ise CFG ile ifade edilebilen içerikten bağımsız dillerdir (context free languages). Bu dillerin özelliği A → γ şeklinde gösterilmeleridir. Buradaki γ değeri sonlular (terminals) ve devamlılar (nonterminals) olabilmektedir. Bu diller aşağı sürüklemeli otomatlar (push down automata PDA) tarafından kabul edilen dillerdir ve hemen hemen bütün programlama dillerinin temelini oluşturmaktadırlar. (programlama dillerinin neredeyse tamamı bu seviye kurallarına uymaktadırlar)

Tip-3 diller ise düzeli ifadeler (regular expressions) ile ifade edilebilen (veya üretilebilen veya parçalanabilen (parse) ) dillerdir. Bu dillerin farkı

A → α ve

A → αB

şeklindeki kurallar ile göterilebilmeleridir.

Yukarıdaki bu tanımları bir tabloda toplamak gerekirse:

Seviye

Dil Örneği

Otomat Uygulaması

Kuralları

Type-0 Recursively enumerable Turing machine α → β
Type-1 Context-sensitive Linear-bounded non-deterministic Turing machine αAβ → αγβ
Type-2 Context-free Non-deterministic pushdown automaton A → γ
Type-3 Regular Finite state automaton A → α ve A → αB

Yukarıdaki seviyeler bütün dilleri kapsamak için yeterli değildir ayrıca yukarıda gösterilen seviyelere giren yukarıdaki tablo dışında diller de bulunmaktadır.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Yazıda çeşitli chomsky hiyerarşisine örnek dilleri vermeye çalışmıştım (regular expressions, pda, fsa gibi). BU dillere örnekler ise ilgili bağlantılara tıkladığınızda çıkan yazılarda bulunuyor. Yine de özel bir örnek ihtiyacınız varsa bu konuda yardımcı olmaya çalışırım.

    başarılar

  2. Cigdem

    Öncelikle cevap verdiginiz icin tsk ediyorum. Söyle anlatmaya calisayim. Diyelim ki Gramer verilmis:
    S ->a
    S->b
    S->(S)
    S->SS
    S->S|S
    S->S*

    Bu Typ 2 mi oluyor? Typ leri birbirinden ayirmakta zorlaniyorum.

  3. Şadi Evren ŞEKER Article Author

    Dil biraz karmaşık olarak yazılmış. SAnırım aşağıdaki şekilde toplamakta yarar var:

    S -> (S) | SS | S* | a | b

    şimdi sorunuza geçecek olursak. Öncelikle bilmemiz gerekir ki, üst seviyede olan diller alt seviyeyi kapsar. Örneğin tip 3 ile yazabildiğimiz herşeyi tip 2 ile yazabiliriz. Dolayısıyla yukarıdaki soru en düşük hangi tipteki gösterim ile yazılabilir diye sormalıyız.

    Yukarıdaki örnek, düzenli ifade olarak yazılabilen (regular expression) dolayısıyla tip 3 olan bir dildir. Yazılmış hali aşağıda verilmiştir:

    S = (a|b)*

    Şayet tiplere göre tasnif sorunu yaşıyorsanız, tavsiyen pompalama önsavını (pumping lemma) çalışmanızdır. Sitede iki pomplama önsavı yazısı yayınlamıştım:
    http://www.bilgisayarkavramlari.com/2009/03/22/duzenli-ifadelerde-pompalama-onsavi-pumping-lemma-for-regular-expressions/
    http://www.bilgisayarkavramlari.com/2009/03/22/icerik-bagimsiz-gramerler-icin-pompalama-onsavi-pumping-lemma-for-context-free-grammers/

    Şayet diliniz yukarıdaki düzenli ifadeler için olan önsava uyuyorsa o zaman tip 3 diyebilirsiniz. Uymuyorsa içerikten bağımsız diller için olan önsava bakınız. Uyuyorsa tip 2 diyebilirsiniz. Buna da uymuyorsa o zaman büyük ihtimalle tip 1’dir.
    Tip 1 ve Tip 0 arasındaki ayırım için Turing makinesi (Turing machine) tasarlanıp tasarlanmadığına bakmanız gerekir.

    Başarılar

  4. enes

    Paylasiminiz icin öncelikle tesekkeür ederim, verdiginiz linklerde regülär veya kontextfrei olmadigini ispatlamak icin pumping lemma yi kullaniyoruz fakat bir dilin kontextfrei oldugunu anlamak icin(karsi bir tez olusturmadan) Chomsky-Schützenberger methodu ile nasil ispatlayabiliriz bir örnek verirseniz cok sevinirim..

Bir cevap yazın

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