[14.03.11] Лекция №6 (Конспекты - Теория формальных языков)

Лекция №6 [14.03.11]

Приведённая форма КС грамматик

1. Удаление -правил

Правило КС грамматики называется -правилом, если оно имеет вид: ,

Любая КС грамматика может быть преобразована к эквивалентной КС грамматике, множество правил вывода которой не содержит -правил (кроме )

Пример:

тогда:

множество правил грамматики станет таким:

Этот пример показывает, что если есть правило , то надо посмотреть цепочки, где это присутствует и произвести замены.

Ещё пример:

Для данной грамматики удаление -правил придётся проводить в два этапа, поскольку имеется правило и имеется вывод . Нужно знать множество всех нетерминалов, из которых выводится пустая цепочка.

Пусть

, ,

- некоторая цепочка в объединённом алфавите, которая не содержит нетерминалов из множества

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

, добавляем , и так далее, последней будет . Только надо рассмотреть все возможные замены на

Если в процессе удаления появляются правила вида или при , то такие правила удаляются.

Рекуррентная процедура вычисления множества : сформируем множество (множество таких нетерминалов грамматики, из которых пустая цепочка выводится за один шаг), состоящее из таких нетерминалов грамматики , что

В множество включаются все нетерминалы из и множество нетерминалов таких, что в множестве правил вывода присутствует правило:

В множество входят такие нетерминалы, что дерево вывода пустой цепочки из этих нетерминалов имеет высоту не больше 2.

Продолжая строить таким образом, мы придём к:

Так как количество нетерминалов в грамматике конечно, найдётся такой номер , когда

Если аксиома принадлежит множеству , то в правилах оставляют , а остальное множество -правил удаляют.

Пример:

приступим:

, так как

, так как ,

ну и получилось:

(предпоследние три – все возможные способы замены на )

2. Удаление цепных правил

Правило вывода , где и нетерминалы, называется цепным правилом.

- цепное, оно тут бесполезное, лишнее

Вывод нетерминала из нетерминала ( ), в котором применяются только цепные правила, называется цепным выводом. Который тоже совершенное бесполезный.

Предположим, что для каждого нетерминала в грамматике известно множество , то есть цепной вывод

Попробуем избавиться от него: если есть и , то необходимо предусмотреть непосредственную замену всех нетерминалов из любой цепочкой , которая является правой частью правила

Рассмотрим алгоритм построения множества :

- множество всех таких нетерминалов , для которых существует цепной вывод длины не больше

Последним будет

Пример:

, где - не просто одна буква, а число или выражение

и

- стартовая

тогда:

, так как

, так как

получилось:

теперь удаляем цепные правила:

Если в процессе обработки появляются правила типа , то оно удаляется.

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

Более развесистый пример:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

удаляем -правила:

- всё, больше нетерминалов нет

получилось:

- здесь можно, потому что стартовая

- здесь уже не надо, оно удаляется

видно, что в результате удаления -переходов возникли цепные правила

, ,

, ,

, ,