GNF, Greibach normal formunu ifade eder. Bir CFG (bağlamdan bağımsız dilbilgisi), tüm üretim kurallarının aşağıdaki koşullardan birini karşılaması durumunda GNF'dedir (Greibach normal biçimi):

• ε üreten bir başlangıç ​​sembolü. Örneğin, S → ε.
• Terminal olmayan bir terminal oluşturur. Örneğin, A → a.
• Herhangi bir sayıda terminal olmayanın takip ettiği bir terminal üreten bir terminal olmayan. Örneğin, S → aASB.

Örneğin:

 G1 = aB, A → aA G2 = S → aAB 

Dilbilgisi G1'in üretim kuralları GNF için belirtilen kuralları karşılar, dolayısıyla G1 dilbilgisi GNF'dedir. Ancak Dilbilgisi G2'nin üretim kuralı, GNF için belirtilen kuralları karşılamamaktadır: A → ε ve B → ε ε içerir (yalnız başlangıç ​​sembolü ε üretebilir). Yani G2 dilbilgisi GNF'de değil.

CFG'yi GNF'ye dönüştürme adımları

Aşama 1: Dilbilgisini CNF'ye dönüştürün.

Verilen gramer CNF'de değilse, onu CNF'ye dönüştürün. CFG'yi CNF'ye dönüştürmek için aşağıdaki konuya başvurabilirsiniz: Chomsky normal formu

Adım 2: Dil bilgisinin sol özyinelemesi varsa, onu ortadan kaldırın.

Bağlamdan bağımsız dilbilgisi sol yineleme içeriyorsa, onu ortadan kaldırın. Sol özyinelemeyi ortadan kaldırmak için aşağıdaki konuya başvurabilirsiniz: Sol Özyineleme

Aşama 3: Dilbilgisinde verilen üretim kuralını GNF formuna dönüştürün.

Dilbilgisindeki herhangi bir üretim kuralı GNF biçiminde değilse dönüştürün.

Örnek:

 S → XB | AA A → a | SA B → b X → a 

Çözüm:

Verilen gramer G zaten CNF'de olduğundan ve sol yineleme olmadığından, 1. ve 2. adımı atlayıp doğrudan 3. adıma gidebiliriz.

A → SA üretim kuralı GNF'de değildir, bu nedenle S → XB | A → SA üretim kuralındaki AA şu şekildedir:

 S → XB | AA A → a | XBA | AAA B → b X → a 

S → XB ve B → XBA üretim kuralı GNF'de değildir, dolayısıyla S → XB ve B → XBA üretim kuralında X → a'yı şu şekilde değiştiririz:

 S → aB | AA A → a | aBA | AAA B → b X → a 

Şimdi sol özyinelemeyi (A → AAA) kaldıracağız, şunu elde edeceğiz:

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Şimdi boş C → ε üretimini kaldıracağız, şunu elde edeceğiz:

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

S → AA üretim kuralı GNF'de değildir, bu nedenle A → aC | aBAC | bir | S → AA üretim kuralındaki aBA şu şekilde:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

C → AAC üretim kuralı GNF'de değildir, bu nedenle A → aC | aBAC | bir | Üretim kuralı C'de aBA → AAC şu şekilde:

Java'da dönüş türü

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

Dolayısıyla bu, G grameri için GNF biçimidir.