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

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

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

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

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

*X ни для каких , (N 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

X

и 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

(N 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).

 

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

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

Содержание раздела

---

---