Контекстная грамматика?

Question

У меня есть проблема, когда мне нужно конвертировать следующий CFG в CFG в CNF.

S-> ABa
A-> aab
B-> Ac

Я знаю, что шаги следующие.

1. Удалить эпсилон-переходы - Готово
2. удалить единицу продукции
3. конвертировать в CNF:
   1. ввести новый нетерминал для каждого термина
   2. заменить терминалы в правилах производства новым нетерминалом
   3. вводит новые нетерминалы для сокращения длины правой стороны каждого производства

Я немного запутался в том, как бы я справился с вышеуказанной проблемой. В основном я запутался в шаге 2 и в производстве юнитов.

Answer 1

S->ABa
C.N.F. is :
M->AB
Z->a
S->MZ

A->aab
C.N.F. is :
X->aa
Y->b
A->XY

B->Ac
C.N.F. is:
K->a
B->AK

Answer 2

Я знаю, что шаги следующие.

1. Удалить эпсилон-переходы - Готово
2. удалить единицу продукции
3. конвертировать в CNF: 1. ввести новый нетерминал для каждого термина
   1. заменить терминалы в правилах производства новым нетерминалом
   2. вводит новые нетерминалы для уменьшения длины правой стороны каждого производства

Шаги 1 и 2 уже выполнены. Так что нам нужно беспокоиться только об шаге 3.

Начальная грамматика:

S-> ABa
A-> aab
B-> Ac

1. Ввести новый нетерминал для каждого термина.

   S  -> ABa
   A  -> aab
   B  -> Ac
   C  -> a
   D  -> b
   E  -> c
   

2. Замените терминалы в правилах производства новым нетерминалом.

   S  -> ABC
   A  -> CCD
   B  -> AE
   C  -> a
   D  -> b
   E  -> c
   

3. Ввести новые нетерминалы, чтобы уменьшить длину правой стороны каждого произведения.

   S  -> AF
   A  -> CG
   B  -> AE
   C  -> a
   D  -> b
   E  -> c
   F  -> BC
   G  -> CD