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

Вход: Приведенная КC-грамматика .

Выход: - грамматика в нормальной форме Хомского.

Метод:

1. ,;

2. Если во множестве правил встречается правило вида

,

где

.

Тогда данное правило добавляется во множество правил без изменений;

3. Если во множестве правил встречается правило вида

,

где

, .

Тогда данное правило добавляется во множество правил без изменений;

4. Если во множестве правил встречается правило вида

,

где

- целевой символ грамматики и не встречается в правых частях других правил.

Тогда данное правило добавляется во множество правил без изменений;

5. Если во множестве правил встречается правило вида

,

где

, .

Тогда во множество правил добавляются правила вида

;

.

Во множество нетерминалов добавляется новый нетерминал вида , т.е.

;

6. Если во множестве правил встречается правило вида

,

где

, .

Тогда во множество правил добавляются правила вида

;

.

Во множество нетерминалов добавляется новый нетерминал вида , т.е.

;

7. Если во множестве правил встречается правило вида

,

где

, .

Тогда во множество правил добавляются правила вида

;

;

.

Во множество нетерминалов добавляются новые нетерминалы вида , , т.е.

;

8. Если во множестве правил встречаются правила вида

,

где

, .

Тогда во множество правил добавляются правила вида

;

;

.

Во множество нетерминалов добавляются новые нетерминалы вида , т.е.

.

Если , то в правых частях добавляемых правил заменяется на новый нетерминал , который добавляется в , а во множество правил добавляются правила вида

.

Если , то не производим никаких замен, все остается без изменений;

9. , грамматика является грамматикой в нормальной форме Хомского.

Пример:

.

Решение:

1. ;

2. Правила вида переносятся в без изменений.

;

;

3. Правила вида переносятся в без изменений.

;

;

;

4. Правила вида переносятся без изменений. Правила такого вида отсутствуют;

5. заменяем на правила вида

;

.

И множество .

заменяем на правила вида

;

.

И множество ;

6. заменяем на правила вида

;

;

И множество ;

7. заменяем на правила вида

;

;

;

И множество ;

заменяем на правила вида

;

;

;

;

;

И множество .

заменяем на правила вида

;

;

И множество .

В результате получаем грамматику со следующими правилами

.

Дата добавления: 2014-01-07