Нормальная форма Грейбаха

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

А → б

A → bD ₁ … D _n

S → ε

где A, D ₁ , ...., D _n - нетерминалы, а b - терминал.

Алгоритм преобразования CFG в нормальную форму Грейбаха

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

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

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

Step 4 - Убрать всю прямую и косвенную левую рекурсию.

Step 5 - Сделайте правильную замену продукции, чтобы преобразовать ее в надлежащую форму GNF.

Проблема

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

S → XY | Xn | п

X → mX | м

Y → Xn | о

Решение

Вот, Sне отображается справа от любого производства, и в наборе производственных правил нет единичных или нулевых производств. Итак, мы можем пропустить Шаг 1 к Шагу 3.

Step 4

Теперь после замены

X в S → XY | Xo | п

с участием

mX | м

мы получаем

S → mXY | МЫ | mXo | мес | п.

И после замены

X в Y → X _n | о

с правой стороны

X → mX | м

мы получаем

Y → mXn | мин | о.

К производственному набору добавлены две новые постановки O → o и P → p, а затем мы пришли к окончательному GNF следующим образом:

S → mXY | МЫ | mXC | mC | п

X → mX | м

Y → mXD | мД | о

О → о

P → p