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

   A → aAb | ab;
   В → АА | A | a.

   4.5.3. Построение грамматики с продуктивными нетерминалами
    Нетерминальный символ А называется непродуктивным (непроизводящим), если он не
порождает ни одной терминальной цепочки, т.е. не существует вывода А →* х, где х∈V*T.
Поэтому представляет интерес удаление из грамматики             всех непродуктивных
нетерминальных символов. Рассмотрим, как для произвольной КС-грамматики можно
построить эквивалентную КС-грамматику, все нетерминальные символы которой
продуктивны. С этой целью выделяется множество W1={A | A → ϕ ∈ P, ϕ ∈ V*T}. Затем
строится множество W1, W2, . . . , Wn+1 по следующим правилам:
    Wn+1 = Wn ∪{BB → x ∈ P, x ∈ (VT ∪ Wn)*}.
    Пусть задана грамматика G со следующими правилами вывода: S → SA | BSb | bAb; A →
aSa | bb; B → bBb | BaA. Построим множество продуктивных нетерминалов:
    W1 = {A}, т.к. в множестве P есть правило A → bb;
    W2 = {A, S}, т.к. имеется правило S → bAb и A ∈ W1;
    W3 = W2.
    Все символы множества VN\Wn являются непродуктивными, не используются в выводе
никакой терминальной цепочки и их можно удалить из грамматики вместе со всеми
правилами, в которые они входят. Грамматика G1, эквивалентная исходной грамматике,
будет включать следующее множество правил:
    S → SA | bAb; A → aSa | bb.
    В грамматике G1 все нетерминалы продуктивны.

   4.5.4. Построение грамматики, аксиома которой зависит от всех нетерминалов
    Существует еще один тип нетерминальных символов, которые можно удалять из
грамматики вместе с правилами, в которые они входят. Например, в грамматике G, заданной
множеством правил P: S → aSb | ba; A → aAa | bba, нетерминал А не участвует ни в каком
выводе, т.к. из аксиомы нельзя вывести цепочку, содержащую этот нетерминал. Поэтому из
заданной грамматики можно удалить нетерминал А. Рассмотрим, как для произвольной КС-
грамматики можно построить эквивалентную КС-грамматику, аксиома которой зависит от
всех нетерминальных символов.
    Для этого построим множество нетерминалов, от которых зависит аксиома. С этой
целью выделим множества W1, W2, . . . , Wn+1 по следующим правилам:
    W1 = {S},
    Wn+1 = Wn ∪{B | A → xBy ∈ P, A ∈ Wn}.
    Нетерминал B∈Wn тогда и только тогда, когда аксиома S зависит от B. Все нетерминалы,
не содержащиеся в Wn, можно удалить из грамматики вместе с правилами, в которые они
входят.
    Пример. Пусть дана КС-грамматика G:
    S → abS | ASa | ab; A → abAa | ab; B → bAab | bB.
    Найдем нетерминалы, от которых зависит аксиома:
    W1 = {S},
    W2 = {S, A}, т.к. имеется правило S → Asa и S ∈ W1;
    W3 = W2.
    Эквивалентная грамматика G1, аксиома которой зависит от всех нетерминальных
символов:
    S → abS | ASa | ab; A → abAa | ab.