Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 21 стр.

              Wi = Wi −1 ∪ { X | X ∈V , ( A → αXβ ) ∈ P, A ∈Wi −1; α , β ∈V *}.
      Шаг 3. Если Wi ≠ Wi −1, то положить i:=i+1 и перейти к шагу 2, иначе счи-
тать W = Wi .
      Шаг 4. Вычислить VN′ = VN ∩ W , VT′ = VT ∩ W , VБ = V − W , P′ = P − PБ ,
где PБ ⊆ P - это множество правил, содержащих недостижимые символы
 X ∈VБ .

       Пример 4.3. Дана грамматика G = ({a, b, c}, {S , B, C}, P, S ) с правилами
P′ : 1) S → ab; 2) B → b; 5) C → cb.
       Преобразуем ее в эквивалентную грамматику G ′ по алгоритму 4.3:
       W0 = {S};
       W1 = {S, a, b};
       W2 = {S, a, b}.
       Т.к. W1=W2, то W={S, a, b}. Множество недостижимых символов
VБ = {B, C , c}. Тогда после удаления недостижимых символов, получим
грамматику G ′ = ({a, b}, {S}, P, S ) с правилом P′ : S → ab.

                     Алгоритм 4.4. Устранение ε-правил
     Вход: КС-грамматика G = (VT , VN , P, S ) .
      Выход: Эквивалентная КС-грамматика G ′ = (VT , VN′ , P′, S ′) без ε-правил
для всех нетерминальных символов, кроме начального, который не должен
встречаться в правых частях правил грамматики.
     Шаг 1. В исходной грамматике G найти ε-порождающие нетерминальные
символы A∈V N , такие, что A ⇒ *ε .
     1.1 Положить N 0 = { A | ( A → ε ) ∈ P} .
      1.2 Вычислить N i = N i −1 ∪ {B | ( B → α ) ∈ P, α ∈ N i*−1} .
      1.3 Если N i ≠ N i −1 , то положить i:=i+1 и перейти к пункту 1.2, иначе
считать N = N i .
      Шаг 2. Из множества P правил исходной грамматики G перенести во
множество        P′     все    правила,     за     исключением       ε-правил, т.е.
P′ = P − {( A → ε ) ∈ P для всех A∈V N }.
      Шаг 3. Пополнить множество P′ правилами, которые получаются из ка-
ждого правила этого множества путем исключения всевозможных комбинаций
ε-порождающих нетерминалов в правой части. Полученные при этом ε-правила
во множество P′ не включать.
      Шаг 4. Если S ∈ N , то P′ = P ∪ {S ′ → ε , S ′ → S }, V N′ = VN ∪ S ′ , где
V ∩ {S ′} = ∅ ; иначе VN′ =V N , S ′ = S .




                                                                                21