Нормальная форма Хомского

Грамматика находится в нормальной форме Хомского (НФХ), все правила грамматики имеют вид A®BC, A®a, где A, B, CÎN и aÎT.

Теорема: Любой e-свободный КС-язык может быть порожден некоторой КС-грамматикой в нормальной форме Хомского.

Доказательство: Предположим, что L - e-свободный КС-язык, порождаемый КС-свободной грамматикой G= (T, N, S, P). Определим эквивалентную её грамматику в форме Хомского.

Алгоритм:

1. Устранение первичных правила, вида A®B.

2. Устранение вторичных правил - это правила, правые части которых есть строки длиной >1 и включающие в себя подстроки терминалов. Если в правой части встречается подцепочка терминалов, то для неё мы вводим новый нетерминал и добавляем соответствующие правило.

Вопросы и упражнения

Пусть задана грамматика G=(T, N, S, P):

S®AaBС

A®baB

B®С

С®e

Постройте эквивалентную ей грамматику в нормальной форме Хомского.