Нормальная форма Хомского

CFG находится в нормальной форме Хомского, если продукция находится в следующих формах:

• А → а
• А → ВС
• S → ε

где A, B и C нетерминалы и a является терминальным.

Алгоритм преобразования в нормальную форму Хомского -

Step 1 - Если стартовый символ S происходит с правой стороны, создайте новый начальный символ S’ и новое производство S’→ S.

Step 2- Удалить пустые постановки. (Использование алгоритма удаления нулевого продукта, описанного ранее)

Step 3- Удалите единичные производства. (Используя описанный ранее алгоритм удаления продукции Unit)

Step 4 - Заменить каждое производство A → B₁…B_n где n > 2 с участием A → B₁C где C → B₂ …B_n. Повторите этот шаг для всех производств, имеющих два или более символов справа.

Step 5 - Если правая сторона какой-либо продукции находится в форме A → aB где a - терминал и A, B нетерминальные, то производство заменяется на A → XB а также X → a. Повторите этот шаг для каждой продукции, которая находится в формеA → aB.

Проблема

Преобразуйте следующий CFG в CNF

S → ASA | aB, A → B | S, B → b | ε

Решение

(1) поскольку S появляется в RHS, мы добавляем новое состояние S₀ а также S₀→S добавляется в производственный набор и становится -

S ₀ → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Теперь мы удалим нулевые постановки -

B → ∈ и A → ∈

После удаления B → ε производственный набор становится -

S ₀ → S, S → ASA | aB | a, A → B | S | ∈, B → b

После удаления A → ∈ производственный набор становится -

S ₀ → S, S → ASA | aB | а | AS | SA | S, A → B | S, B → b

(3) Теперь удалим единичные производства.

После удаления S → S производственный набор становится -

S ₀ → S, S → ASA | aB | а | AS | SA, A → B | S, B → b

После удаления S ₀ → S производственный набор становится -

S ₀ → ASA | aB | а | AS | SA, S → ASA | aB | а | AS | SA

A → B | S, B → b

После удаления A → B производственный набор становится -

S ₀ → ASA | aB | а | AS | SA, S → ASA | aB | а | AS | SA

A → S | б

B → b

После удаления A → S производственный набор становится -

S ₀ → ASA | aB | а | AS | SA, S → ASA | aB | а | AS | SA

A → b | ASA | aB | а | AS | SA, B → b

(4) Теперь мы выясним более двух переменных в RHS.

Здесь S ₀ → ASA, S → ASA, A → ASA нарушает два нетерминала в RHS

Следовательно, мы применим шаг 4 и шаг 5, чтобы получить следующий окончательный производственный набор, который находится в CNF -

S ₀ → AX | aB | а | AS | SA

S → AX | aB | а | AS | SA

A → b | AX | aB | а | AS | SA

B → b

X → SA

(5)Мы должны изменить продукций S ₀ → aB, S → aB, A → aB

И окончательная постановка становится -

S ₀ → AX | YB | а | AS | SA

S → AX | YB | а | AS | SA

A → b A → b | AX | YB | а | AS | SA

B → b

X → SA

Y → а