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