Дифференцирования для контекстно-свободной грамматики

Question

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

S→aSbS∣bSaS∣ε 

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

Замена нетерминалы с клеммами

S→aabb 

S→ε 

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

спасибо.

Answer 1

Как писал @Ashalynd, вы должны прочитать немного more about Chomsky Normal Form:

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

Грамматика у вас есть содержит е и, следовательно, никогда не может быть преобразована в УТС, ε является корректным предложение на языке производимого S.