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
Отже, для даної граматики це необхідна КНФ.