Chomsky Normal Şekili (Chomsky Normal Form)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde özellikle otomatlar (automata) ve dil tasarımında (compiler design) oldukça sık kullanılan konulardan birisi de içerikten bağımsız dilbilgisidir. (Context Free Grammer)

İçerikten bağımsız dil (Context Free Language) konusunda yapılan çalışamlar gelişen ihtiyaçlar ilave bazı kurallar konulmasını gerektirmiştir. Bu konuda çalışan Naom Chomsky tarafından konulan kurallara CNF veya Chomsky normal şekli ismi verilir ve aşağıda açıklanmıştır.

CNF’in tanımı ve kuralları

Şayet bir CFG aşağıdaki kurallara uyuyorsa bu dilbilgisine CNF’e uygun denilebilir. Örneğin bir dilde

A

$\rightarrow\,$

B C

veya

A

$\rightarrow\,$ α veya

S

$\rightarrow\,$ λ

şeklinde kurallara uyuyorsa. (Burada ABC birer devamlı (nonterminal) α bir sonlu (terminal) ve λ ise boş dizgi (empty string) gösteren sembollerdir). Burada B ve C sembolleri başlangıç sembolü olamaz. Yani

B $\rightarrow\,$ α

gibi bir kural dilbilgisinde bulunamaz. Benzer şekilde

A $\rightarrow\,$ BCC

şeklinde bir gösterim de CNF kurallarına aykırıdır (en fazla 2 devamlı (nonterminal) bulunabilir).

Yukarıdaki tanımdan anlaşılacağı üzere CNF kulllarına uygun olan her dil zaten CFG’dir. Ayrıca yine yukarıdaki tanıma dayanarak bir dildeki bir cümlenin parçalanması (parse) işlemi sırasındaki her adım, kendinden bir önceki adıma göre en fazla bir harf uzun olabilir. Bunun sebebi yukarıdaki şekilde yazılan bir dilde en fazla 2 devamlı (nonterminal) bulunacağı ve dolayısıyla en fazla 1 harf ilave edileceğidir.

Diğer bir ifadeyle CNF’e uygun bir dil parçalaranar bir parçalama ağacı (parse tree) oluşturulduğunda ortaya bir ikili ağaç (binary tree) çıkar ve bu ağacın en derin olma durumunda parçalanan kelimenin boyutundan 1 eksik (ilk devamlı açılımının (nonterminal) 2 elemanlı olduğu düşünülürse) ve en sığ olma durumunda da yine kelime boyutundan 1 eksik olacaktır. Daha kesin bir ifadeyle CNF’e uygun bir dil ile parçalanan bir kelime ve oluşan parçalama ağacında (parse tree) belirsizlik (ambiguity) bulunamaz ve her zaman tek bir ağaç çıkar.

Bir CFG’nin CNF’e çevrimi

Yukarıdaki açıklamalar ışığında her CFG’nin CNF yapısında olmadığını öğrendik. Ayrıca her CFG’nin CNF yapısına çevrilebileceği de bir gerçektir. Bu durumda herhangi bir CFG’nin CNF’e çevrimi için aşağıdaki 5 farklı durum ve bu 5 farklı durumun çözümü verilmiştir.

1. Durumda başlangıcın sağ tarafta bulunmasına karşılık ilave bir başlangıç devamlısı (nonterminal) eklenir.

Örneğin dilimiz aşağıdaki şekilde olsun:

$S$ $\rightarrow\,$ $ASA$ | aB

$A$ $\rightarrow\,$ $B$ | S

$B$ $\rightarrow\,$ $b$ | λ

Yukarıdaki dilbilgisi tanımında görüleceği üzere iki noktada S yani başlangıç devamlısı (nonterminal) sağ tarafta bulunmaktadır. Çözüm olarak ilave bir devamlı eklenerek aşağıdaki hale getirilebilir:

S_$0$ $\rightarrow\,$ S

$S$ $\rightarrow\,$ $ASA$ | aB

$A$ $\rightarrow\,$ $B$ | S

$B$ $\rightarrow\,$ $b$ | λ

Yukarıdaki bu yeni haliyle başlangıç geçişlisi artık S0 olmuştur ve artık sağ tarafta istenmeyen bu terim bulunmamaktadır.

2. durumda lambda (λ) terimlerinin temizlenmesi gerekir. Bu problemin çözümü için devamlılardan (nonterminal) başlanarak alternatif sonuçlar sıralanır. Örneğin bir önceki adımda oluşturduğumuz grameri ele alacak olursak:

S_$0$ $\rightarrow\,$ S

$S$ $\rightarrow\,$ $ASA$ | aB

$A$ $\rightarrow\,$ $B$ | S

$B$ $\rightarrow\,$ $b$ | λ

Yukarıdaki gramerde B -> λ terimi bulunmaktadır. Bunu kaldırmak için B devamlısının (nonterminal) kullanıldığı yerlerde değişiklik yapmak gerekir.

S_$0$ $\rightarrow\,$ S

$S$ $\rightarrow\,$ $ASA | aB | AS | SA | S | a$

$A$ $\rightarrow\,$ $B$ | S

$B$ $\rightarrow\,$ $b$

Yukarıdaki S-> $AS | SA | S | a terimleri yeni eklenmiştir. Bu terimler B->$ λ terimi ile üretilebilecek bütün alternatifleri kapsar.

3. Durumda tek terimlerin kaldırılması için tek terimlilerde ulaşılabilen terimler tekrarlanır. Örneğin yukarıdaki gramerin son halinden devam edecek olursak:

S_$0$ $\rightarrow\,$ S

$S$ $\rightarrow\,$ $ASA | aB | AS | SA | S | a$

$A$ $\rightarrow\,$ $B$ | S

$B$ $\rightarrow\,$ $b$

$Gramerinde tek terili olarak$ S_$0$ $\rightarrow\,$ S , $A$ $\rightarrow\,$ $B$ ve $A$ $\rightarrow\,$ S durumları bulunmaktadır. Bu durumların kaldırılması için terim değerleri tekrarlanır :

S₀ $\rightarrow\,$ ASA | aB | AS | SA | a
S $\rightarrow\,$ ASA | aB | AS | SA | a
A $\rightarrow\,$ b | ASA | aB | AS | SA | a
B $\rightarrow\,$ b

Yukarıdaki son halinde S ve B değeri (okun sağ tarafında olan değerler) olduğu gibi kopyalanmıştır.

4. durumda şayet bir devamlının (nonterminal) tanımında karışık bir durum varsa (yani bir sonluyu (terminal) ifade eden terim karışıksa) basitletştirmek için ilave bir devamlı (nonterminal) eklenir. Yine yukarıdaki dilden devam edecek olursak:

S₀ $\rightarrow\,$ ASA | aB | AS | SA | a
S $\rightarrow\,$ ASA | aB | AS | SA | a
A $\rightarrow\,$ b | ASA | aB | AS | SA | a
B $\rightarrow\,$ b

Gramerinde “a” sonlusunun (terminal) değerinin B devamlısı (nonterminal) ile yanyana durduğu aB terimini görüyoruz. Bu karışık bir durumdur ve çözümü için yeni bir devamlı (nonterminal) ilave edilir.

S₀ $\rightarrow\,$ ASA | UB | AS | SA | a
S $\rightarrow\,$ ASA | UB | AS | SA | a
A $\rightarrow\,$ b | ASA | UB | AS | SA | a
B $\rightarrow\,$ b

U $\rightarrow\,$ a

Yukarıdaki şekilde karışık olan bütün aB terimleri düzeltilmiştir.

5. durumda ise uzun terimlerin kısaltılması söz konusudur. Yani okun sağ tarafında en fazla iki devamlı (nonterminal) bir terimde bulunabilir. Örneğin ASA gibi üç devamlı (nonterminal) bulunduğu durumlar CNF için uygun değildir.

S₀ $\rightarrow\,$ ASA | UB | AS | SA | a
S $\rightarrow\,$ ASA | UB | AS | SA | a
A $\rightarrow\,$ b | ASA | UB | AS | SA | a
B $\rightarrow\,$ b

U $\rightarrow\,$ a

dilini ele alırsak

S0 $\rightarrow\,$ AA1 | UB | AS | SA | a
S $\rightarrow\,$ AA1 | UB | AS | SA | a
A $\rightarrow\,$ b | AA1 | UB | AS | SA | a
B $\rightarrow\,$ b
U $\rightarrow\,$ a
A1 $\rightarrow\,$ SA

Tek problemli olan ASA terimi yerine ilave bir devamlı (nonterminal) eklenerek yukarıdaki şekilde düzeltilebilir.

« Kirchoff Teoremi (Kirchoff Theorem) | Sıfır Bilgi İspatı (Zero-Knowledge proof) »

Yorumlar

Toplam 3 yorum var.

tarık-ege.üni | 12 Dec 2009, 01:43
otomata gibi türkiyede fazla değer verilmeyen ama aslında derleyici programlama ve bilgisayar dünyasına yeni bir dil kazandırma konusunda çok önmeli olan bu dersimiz için de kaynaksız bırakmıyorsunuz bizi.teşekkürler….yanlış değilsem ege,bilkent,itü,boğaziçi ,gazi ve odtü tek işliyor bu dersi..
Anonymous | 13 Dec 2009, 15:26
Işık üniversitesinde de var …. Theory of Computation…
Hasan Erdem Yantır | 14 Dec 2009, 23:28
Hemen hemen bütün bilgisayar mühendisliği bölümlerinde otomata dersi var.

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Chomsky Normal Şekili (Chomsky Normal Form)' isimli yazı 22 Jun 2009 tarihinde, saat: 11:29 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 378 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), Programlama Dilleri kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar