CNF означає нормальну форму Хомського. CFG (контекстно-вільна граматика) знаходиться в CNF (нормальній формі Хомського), якщо всі правила виробництва задовольняють одну з таких умов:

• Почніть генерувати символ ε. Наприклад, A → ε.
• Нетермінал, що генерує два нетермінали. Наприклад, S → AB.
• Нетермінал, що генерує термінал. Наприклад, S → a.

Наприклад:

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

Правила створення граматики G1 задовольняють правила, визначені для CNF, тому граматика G1 знаходиться в CNF. Однак правило виробництва Grammar G2 не задовольняє правила, визначені для CNF, оскільки S → aZ містить термінальний, за яким іде нетермінальний. Отже, граматика G2 не в CNF.

parseint java

Кроки для перетворення CFG в CNF

Крок 1: Видаліть символ старту з правого боку. Якщо символ початку T знаходиться праворуч від будь-якої продукції, створіть нову продукцію як:

 S1 → S 

Де S1 – новий символ початку.

крок 2: У граматиці видаліть null, unit і марні постановки. Ви можете звернутися до спрощення CFG.

крок 3: Видаліть термінали з RHS виробництва, якщо вони існують разом з іншими нетерміналами або терміналами. Наприклад, виробництво S → aA можна розкласти як:

матриці в програмуванні на C

 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 з’являється на правій лінії. Граматика буде:

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

крок 2: Оскільки граматика G1 містить A → ε нульове виробництво, його видалення з граматики дає:

10 мл в унціях

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

Тепер, оскільки граматика G1 містить Unit production 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:

що таке hashset java

 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 

Отже, для даної граматики це необхідна КНФ.