ЦНФ означава нормалну форму Чомског. ЦФГ (граматика без контекста) је у ЦНФ (нормалном облику Чомског) ако сва правила производње задовољавају један од следећих услова:

• Започните генерисање симбола ε.
• Нетерминал који генерише два нетерминала. На пример, С → АБ.
• Нетерминал који генерише терминал. На пример, С → а.

На пример:

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

Правила производње Граматике Г1 задовољавају правила наведена за ЦНФ, тако да је граматика Г1 у ЦНФ. Међутим, правило производње Граматике Г2 не задовољава правила специфицирана за ЦНФ јер С → аЗ садржи терминал иза којег следи нетерминал. Дакле, граматика Г2 није у ЦНФ.

понављање мапе у Јави

Кораци за претварање ЦФГ у ЦНФ

Корак 1: Уклоните стартни симбол из РХС-а. Ако је почетни симбол Т на десној страни било које производње, креирајте нову производњу као:

 S1 → S 

Где је С1 нови почетни симбол.

Корак 2: У граматици уклоните нулте, јединичне и бескорисне продукције. Можете погледати Поједностављење ЦФГ-а.

Корак 3: Елиминишите терминале из РХС производње ако постоје са другим не-терминалцима или терминалима. На пример, производња С → аА се може декомпоновати као:

 S → RA R → a 

4. корак: Елиминишите РХС са више од два не-терминала. На пример, С → АСБ се може декомпоновати као:

 S → RS R → AS 

Пример:

Конвертујте дати ЦФГ у ЦНФ. Размотрите дату граматику Г1:

груписање

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

Решење:

Корак 1: Направићемо нову производњу С1 → С, пошто се почетни симбол С појављује на РХС-у. Граматика ће бити:

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

Корак 2: Како граматика Г1 садржи А → ε нулту производњу, њено уклањање из граматике даје:

стринг.формат у јава

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

Сада, пошто граматика Г1 садржи јединичну производњу С → Б, њен принос уклањања:

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

Такође уклоните јединичну производњу С1 → С, њено уклањање из граматике даје:

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

Корак 3: У производном правилу С0 → аА | Аа, С → аА | Аа, А → аББ и Б → Аа, терминал а постоји на РХС са не-терминалима. Дакле, заменићемо терминал а са Кс:

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

4. корак: У производном правилу А → КСББ, РХС има више од два симбола, уклањајући га из граматичког приноса:

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

Дакле, за дату граматику, ово је потребан ЦНФ.

множење матрице у в