Преобразования КС-грамматик

Рассмотрим ряд преобразований, позволяющих «улучшить» вид контекстно-свободной грамматики, без изменения порождаемого ею языка.

Назовем символ X

T) недостижимым в КС-грамматике G = (N, T, P, S), если X не появляется ни в одной выводимой цепочке этой

грамматики. Иными словами, символ X является недостижимым, если в G не существует вывода S

ни для каких

T)*.

Алгоритм 4.1. Устранение недостижимых символов.

Вход. КС-грамматика G = (N, T, P, S).

Выход. КС-грамматика G' = (N', T', P', S) без недостижимых символов, такая, что L(G') = L(G).

Метод. Выполнить шаги 1-4:

Положить V 0 = {S} и i = 1.

Положить V i = {X | в P есть A

и A

V i-1}

V i-1.

Если V i

V i-1, положить i = i+1 и перейти к шагу 2. В противном случае перейти к шагу 4.

Положить N' = V i

N, T' = V i

T. Включить в P' все правила из P, содержащие только символы из V i.

Назовем символ X

T) бесполезным в КС-грамматике G = (N, T, P, S), если в ней не существует вывода вида S

*xXy

*xwy, где w, x, y принадлежат T*. Очевидно, что каждый недостижимый символ является бесполезным.

Алгоритм 4.2. Устранение бесполезных символов.

Вход. КС-грамматика G = (N, T, P, S).

Выход. КС-грамматика G' = (N', T', P', S) без бесполезных символов, такая, что L(G') = L(G).

Метод. Выполнить шаги 1-5:

Положить N0 =
и i = 1.
Положить Ni = {A|A

P и

(Ni-1
T)*}
Ni-1.

Если Ni
Ni-1, положить i = i+1 и перейти к шагу 2. В противном случае положить Ne = Ni и перейти к шагу 4.

Положить G1 = ((N
Ne)
{S}, T, P1, S), где P1 состоит из правил множества P, содержащих только символы из Ne
T.

Применив к G1 алгоритм 4.1, получить G' = (N', T', P', S).

КС-грамматика без бесполезных символов называется приведенной. Легко видеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые

грамматики - приведенные.

Все публикации раздела