Алгоритм удаления пустых правил

Вход: КС-грамматика .

Выход: Грамматика без пустых правил.

Метод:

1. , ;

2. ;

3. Если , то переходим к шагу 4;

если , то и переходим к шагу 2;

4. ;

;

- содержит все правила из .

5. Если в новом множестве правил присутствует правило вида , причем элементы цепочки содержат символы из построенного множества , то в новое множество правил добавляются правила вида , где - цепочка, которая формируется из цепочки путем исключения всевозможных комбинаций элементов , кроме пустых правил.

6. Если целевой символ исходной грамматики попал в построенное множество , т.е. , то во множество правил результирующей грамматики добавляются правила вида , и целевым символом грамматики будет новый символ .

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