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

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 и т. Д.

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

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