Greibach Normal Formu
Üretimler aşağıdaki biçimlerde ise bir CFG Greibach Normal Formundadır -
A → b
A → bD 1 … D n
S → ε
burada A, D 1 , ...., D n terminal değildir ve b bir terminaldir.
Bir CFG'yi Greibach Normal Formuna Dönüştürme Algoritması
Step 1 - Başlangıç sembolü S sağ tarafta ortaya çıkarsa, yeni bir başlangıç sembolü oluştur S’ ve yeni bir üretim S’ → S.
Step 2- Null yapımları kaldırın. (Daha önce tartışılan Boş üretim kaldırma algoritmasını kullanma)
Step 3- Birim üretimleri kaldırın. (Daha önce tartışılan Birim üretim kaldırma algoritmasını kullanarak)
Step 4 - Tüm doğrudan ve dolaylı sol özyinelemeleri kaldırın.
Step 5 - GNF'nin uygun biçimine dönüştürmek için üretimlerin uygun ikamelerini yapın.
Sorun
Aşağıdaki CFG'yi CNF'ye dönüştürün
S → XY | Xn | p
X → mX | m
Y → Xn | Ö
Çözüm
Buraya, Sherhangi bir üretimin sağ tarafında görünmez ve üretim kural setinde birim veya boş üretim yoktur. Yani 1. Adımdan 3. Adıma atlayabiliriz.
Step 4
Şimdi değiştirdikten sonra
X in S → XY | Xo | p
ile
mX | m
elde ederiz
S → mXY | mY | mXo | mo | s.
Ve değiştirdikten sonra
Y'de X → X n | Ö
sağ tarafı ile
X → mX | m
elde ederiz
Y → mXn | mn | Ö.
Üretim setine iki yeni yapım O → o ve P → p eklendi ve ardından aşağıdaki gibi son GNF'ye geldik -
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | Ö
O → o
P → p