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

Удаление недостижимых символов

Определение: Символ является недостижимым, если он не появляется в правых частях правил данной грамматики.

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

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

Метод:

1. ;

2. ;

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

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

4. ;

;

;

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

.

Пример:

.

Решение:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

;

- Целевой символ

.

Дата добавления: 2014-01-07; Просмотров: 1497; Нарушение авторских прав?; Мы поможем в написании вашей работы!