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.