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

ABC veya

Aα veya

Sλ

ş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 α

gibi bir kural dilbilgisinde bulunamaz. Benzer şekilde

A 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:

SASA | aB

AB | S

Bb | λ

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₀ S

SASA | aB

AB | S

Bb | λ

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₀ S

SASA | aB

AB | S

Bb | λ

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₀ S

SASA | aB | AS | SA | S | a

AB | S

Bb

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₀ S

SASA | aB | AS | SA | S | a

AB | S

Bb

Gramerinde tek terili olarak S₀ S , AB ve AS durumları bulunmaktadır. Bu durumların kaldırılması için terim değerleri tekrarlanır :

S₀ ASA | aB | AS | SA | a
S ASA | aB | AS | SA | a
A b | ASA | aB | AS | SA | a
B 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₀ ASA | aB | AS | SA | a
S ASA | aB | AS | SA | a
A b | ASA | aB | AS | SA | a
B 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₀ ASA | UB | AS | SA | a
S ASA | UB | AS | SA | a
A b | ASA | UB | AS | SA | a
B b

U 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₀ ASA | UB | AS | SA | a
S ASA | UB | AS | SA | a
A b | ASA | UB | AS | SA | a
B b

U a

dilini ele alırsak

S0 AA1 | UB | AS | SA | a
S AA1 | UB | AS | SA | a
A b | AA1 | UB | AS | SA | a
B b
U a
A1 SA

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