CNF, Chomsky normal formunu ifade eder. Tüm üretim kuralları aşağıdaki koşullardan birini karşılıyorsa, bir CFG (bağlamdan bağımsız dilbilgisi), CNF'dedir (Chomsky normal biçimi):

• ε sembolü oluşturmaya başlayın. Örneğin, A → ε.
• İki terminal olmayan üreten bir terminal olmayan. Örneğin, S → AB.
• Terminal olmayan bir terminal oluşturur. Örneğin, S → a.

Örneğin:

 G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 

Dilbilgisi G1'in üretim kuralları CNF için belirtilen kuralları karşılar, dolayısıyla G1 dilbilgisi CNF'dedir. Bununla birlikte, Dilbilgisi G2'nin üretim kuralı, CNF için belirtilen kuralları karşılamamaktadır çünkü S → aZ, terminal ve ardından terminal olmayanı içermektedir. Yani G2 dilbilgisi CNF'de değil.

ikili ağacın sıralı geçişi

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

Aşama 1: RHS'den başlatma sembolünü kaldırın. Başlangıç ​​sembolü T herhangi bir üretimin sağ tarafındaysa, şu şekilde yeni bir üretim oluşturun:

 S1 → S 

Burada S1 yeni başlangıç ​​sembolüdür.

Adım 2: Dilbilgisinde boş, birim ve işe yaramaz yapımları kaldırın. CFG'nin Basitleştirilmesine başvurabilirsiniz.

char'ı string java'ya dönüştür

Aşama 3: Diğer terminal olmayan veya terminallerle birlikte mevcut olmaları durumunda, terminalleri üretimin RHS'sinden çıkarın. Örneğin, S → aA üretimi şu şekilde ayrıştırılabilir:

 S → RA R → a 

Adım 4: İkiden fazla terminal olmayan RHS'yi ortadan kaldırın. Örneğin, S → ASB şu şekilde ayrıştırılabilir:

 S → RS R → AS 

Örnek:

Verilen CFG'yi CNF'ye dönüştürün. Verilen gramer G1'i düşünün:

 S → a | aA | B A → aBB | ε B → Aa | b 

Çözüm:

Aşama 1: Sağdaki S başlangıç ​​sembolü göründüğü için yeni bir S1 → S üretimi oluşturacağız. Dilbilgisi şöyle olacaktır:

 S1 → S S → a | aA | B A → aBB | ε B → Aa | b 

Adım 2: G1 grameri A → ε null üretimi içerdiğinden, bunun gramerden çıkarılması şunu sağlar:

java'da string.format

 S1 → S S → a | aA | B A → aBB B → Aa | b | a 

Şimdi, G1 grameri Birim üretimi S → B'yi içerdiğinden, çıkarma verimi:

 S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a 

Ayrıca S1 → S birim üretimini de kaldırın, bunun gramerden çıkarılması şunu sağlar:

 S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a 

Aşama 3: Üretim kuralında S0 → aA | Aa, S → aA | Aa, A → aBB ve B → Aa, RHS'de terminal olmayan terminaller ile terminal a mevcuttur. Böylece a terminalini X ile değiştireceğiz:

 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

Adım 4: A → XBB üretim kuralında, RHS'nin ikiden fazla sembolü vardır ve bu da onu gramer veriminden çıkarır:

if else ifadeleri java

 S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB 

Dolayısıyla verilen gramer için bu gerekli CNF'dir.