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.