Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 31 стр.

    В эквивалентную грамматику будут включены правила вида А → w, A∈VN; w∈(VT ∪
VN)*, если из вершины с меткой А существует путь в вершину с меткой w.
    S → aFb | aSb | аА;
    А → аА | aSb | aFb;
    В → аА | aSb | aFb;
    F → bc | bFc.
       Получено то же множество правил Р, что и аналитическим методом.

      4.5.2. Построение неукорачивающей грамматики

    Грамматика, не содержащая правил с пустой правой частью, называется
неукорачивающей грамматикой.
    В грамматике с правилами вида А→ε длина выводимой цепочки при переходе от k-го
шага к (k+1)-му уменьшается. Поэтому грамматики с правилами вида А→ε называются
укорачивающими. Восходящий синтаксический разбор в укорачивающих грамматиках
сложнее по сравнению с разбором в неукорачивающих грамматиках, т.к. при редукции
необходимо отыскать такой фрагмент входной цепочки, в которую можно вставить пустой
символ.
    Покажем, что для произвольной КС-грамматики, порождающей язык без пустой
цепочки, можно построить эквивалентную неукорачивающую КС-грамматику.
    Построим множество всех нетерминальных символов грамматики G=(VT, VN, P, S), из
которых выводится пустая цепочка, выделив следующие множества:
    W1= {A | A→ε ∈ P},
     Wn+1 = Wn ∪{B | B→ϕ ∈ P, ϕ ∈ W*n }.
    Затем найдем множество правил эквивалентной грамматики в два этапа:
    а) удалив из множества P исходной грамматики правила с пустой правой частью P1' = P\{
A→ε | A→ε ∈ P};
    б) получив новые правила A→ϕ' после удаления из каждого правила исходной
грамматики A→ϕ ∈ P те нетерминалы, которые вошли в множество Wn по правилу:
    P1" = { A→ϕ' | A→ϕ ∈ P'; ϕ =ϕ1Bϕ2 | B∈Wn; ϕ'=ϕ1Bϕ2}.
    Повторив п.б) для каждого нетерминала, принадлежащего множеству Wn, получим
эквивалентную грамматику G = (VT, VN, Pэ, S).
    Пример. Пусть задана грамматика G со следующими правилами вывода: S → АbА | сАb |
Bb; А → аАb | ε; В→АА|а. Необходимо:
    1) построить множество нетерминалов, из которых выводится ε;
    2) построить неукорачивающую грамматику, эквивалентную исходной.
    Для того чтобы построить множество всех нетерминалов грамматики, из которых
выводится пустая цепочка, выделим следующие множества:
    W1 = {А | А → ε ∈ P};
    Wm+1 = Wm ∪ {В | В → ϕ ∈ Р, ϕ ∈ W*m}.
    Так как мы имеем правило А → ε ∈ Р, то можно построить множество W1 = {A},
включающее нетерминал А.
    Построим множество W2. С нетерминалом А связан нетерминал В, т.е. существует
правило В → АА и А ∈ W1. Следовательно, W2={A,B}.
    W3 = W2, т. к. множество W3={В|В → ϕ ∈ Р, ϕ ∈ W*m } является пустым.
    Исключив правило, содержащее пустую цепочку в правой части, получим
неукорачивающую грамматику G1 следующего вида:
    S → АbА | сАb | Bb | bA | Ab | cb | b;