ЦНФ означава нормалну форму Чомског. ЦФГ (граматика без контекста) је у ЦНФ (нормалном облику Чомског) ако сва правила производње задовољавају један од следећих услова:
- Започните генерисање симбола ε.
- Нетерминал који генерише два нетерминала. На пример, С → АБ.
- Нетерминал који генерише терминал. На пример, С → а.
На пример:
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
Дакле, за дату граматику, ово је потребан ЦНФ.
множење матрице у в