CNF означава нормална форма на Чомски. CFG (граматика без контекст) е в CNF (нормална форма на Чомски), ако всички производствени правила отговарят на едно от следните условия:

• Стартирайте символа, генериращ ε, например A → ε.
• Нетерминал, генериращ два нетерминала. Например S → AB.
• Нетерминал, генериращ терминал. Например S → a.

Например:

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

Правилата за производство на Grammar G1 отговарят на правилата, определени за CNF, така че граматиката G1 е в CNF. Въпреки това, производственото правило на Grammar G2 не отговаря на правилата, определени за CNF, тъй като S → aZ съдържа терминал, последван от не-терминал. Така че граматиката G2 не е в CNF.

java за разделяне на низове

Стъпки за конвертиране на CFG в CNF

Етап 1: Елиминирайте стартовия символ от RHS. Ако началният символ T е от дясната страна на която и да е продукция, създайте нова продукция като:

 S1 → S 

Където S1 е новият стартов символ.

Стъпка 2: В граматиката премахнете нулевите, единиците и безполезните продукции. Можете да се обърнете към опростяването на CFG.

Стъпка 3: Елиминирайте терминалите от RHS на продукцията, ако съществуват с други нетерминали или терминали. Например производството S → aA може да се разложи като:

каква е файловата система на linux

 S → RA R → a 

Стъпка 4: Елиминирайте RHS с повече от два нетерминала. Например S → ASB може да се разложи като:

 S → RS R → AS 

Пример:

Преобразувайте дадения CFG в CNF. Разгледайте дадената граматика G1:

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

Решение:

Етап 1: Ще създадем ново производство S1 → S, тъй като символът за начало S се появява на RHS. Граматиката ще бъде:

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

Стъпка 2: Тъй като граматиката G1 съдържа A → ε нулева продукция, премахването й от граматиката дава:

дълго към int java

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

Сега, тъй като граматиката G1 съдържа производство на единица S → B, нейният добив от отстраняване:

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

Също така премахнете производството на единица S1 → S, премахването му от граматиката дава:

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

Стъпка 3: В производственото правило S0 → aA | Aa, S → aA | Aa, A → aBB и B → Aa, терминал a съществува на RHS с не-терминали. Така че ще заменим терминал a с X:

на колко години е Кайли Дженър

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

Стъпка 4: В производственото правило A → XBB, RHS има повече от два символа, което го премахва от граматическия добив:

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

Следователно, за дадената граматика това е необходимата CNF.