Хомская нормальная форма правильности

Question

У меня есть эти постановки:

S->aSb
S-> eps      (eps=empty string)

Я должен применить нормальную форму Хомского

Мои рассуждения:

1) устранить правила eps учитывая:

S->aSb
S-> eps

Я получил:

S->ab

S->aSb

2) устранить единичные правила

Нет ни одного

3) удалить ненужные символы

Я получил:

S->ab

Итак, данная грамматика после применения CNF (нормальная форма Хомского) становится:

S->ab

Я прав?

Answer 1

То, что у вас здесь, не совсем то же самое. Обратите внимание, что пустая строка больше не является частью вашего языка, а также строки aabb, aaabbb и т. Д.

Проверьте шаг, где вы устраняете ненужные правила. Это второе правило действительно бесполезно?

Кроме того, вы уверены, что можете устранить производство эпсилон?