Производные для контекстно-свободной грамматики

Question

Производные для контекстно-свободной грамматики

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

S→aSbS∣bSaS∣ε

Однако я не уверен, правильно ли я делаю деривации - вот что у меня есть:

Замена нетерминалов с терминалами

S→aabb

S→ε

Может кто-нибудь сказать мне, если это правильно / на правильном пути?

Спасибо.

1

context-free-grammar computer-science-theory chomsky-normal-form

Источник

user3000731 05 окт '14 в 20:50

1 ответ

Другие вопросы по тегам context-free-grammar computer-science-theory chomsky-normal-form

user4370109 27 май '15 в 11:30 2015-05-27 11:30 · Answer 1 · 2015-05-27 11:30

Как писал @Ashalynd, вы должны прочитать немного больше о нормальной форме Хомского:

Нормальная форма Хомского означает не эпсилон, и не сложные высказывания.

Имеющаяся у вас грамматика содержит ε и поэтому никогда не может быть преобразована в CNF, так как ε является допустимым предложением на языке, производимом S.