Правильность нормальной формы Хомского

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

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

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

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

1) исключить правила eps. Дано:

S->aSb
S-> eps

Я получил:

S->ab

S->aSb

2) исключить правила юнита

Нет ни одного

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

Я получил:

S->ab

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

S->ab

Я прав?


grammar context-free-grammar chomsky-normal-form
person josè    schedule 06.07.2011    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

person templatetypedef    schedule 06.07.2011
comment
это правильно ... вы правы. Применение CNF подразумевает удаление продукции eps ... но здесь у меня есть только одно правило eps ... Я запутался - person josè; 06.07.2011
comment
Хорошо, правило S- ›eps не может быть исключено, потому что S - это начальный символ .. Значит, все, что я сделал, было неправильно .. - person josè; 06.07.2011
comment
@ josè: На самом деле, вам не нужно удалять все продукты в формате eps. Грамматика в CNF может содержать правило S - ›\ epsilon, где S - начальный терминал, и он не должен встречаться справа от любого производственного правила. - person Martin Jonáš; 06.07.2011
comment
символ .. Значит, все, что я сделал, было неправильно .. Полагаю, все осталось без изменений .. Я прав? Таким образом, конечный результат - S- ›aSb и S-› eps, но это нечто иное, чем наличие A- ›A-› BC, как предполагают спецификации CNF. - person josè; 06.07.2011