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

      4.5.1. Удаление правил вида А → В

     Преобразование первого типа состоит в удалении правил А → В, или <нетерминал> →
<нетерминал>.
     Покажем, что для любой КС-грамматики можно построить эквивалентную грамматику,
не содержащую правил вида: А → В, где А и В - нетерминальные символы.
     Пусть имеется КС-грамматика G=(VT, VN, P, S), где множество нетерминалов VN={A1,
A2, . . . , An}. Разобьем Р на два непересекающихся множества: P = P1 ∪ P2. В P1 включены
все правила вида Аi → Ak, в P2 включены все остальные правила, т.е. P2 = P \ P1. Затем для
каждого Аi определим множество правил P(Аi), включив в него все такие правила Аi→ϕ, что
Аi →* Aj и Аj → ϕ, где Аj → ϕ ∈ P2. Построим эквивалентную КС-грамматику Gэ = (VT, VN,
Pэ, S), в которой множества терминальных и нетерминальных символов, а также аксиома
совпадают с теми же объектами исходной грамматики G, а множество правил Pэ получено
объединением правил множества P2 и правил P(Аi) для всех 1≤ i ≤n:
                      n
              Pэ =   U
                     i=1
                           P ( A i ) ∪ P2 .


    Пример. Пусть задана грамматика G со следующими правилами вывода S → aFb | А; А
→ аА | В; В → aSb | S; F → bc | bFc.
    Построим множества правил Р2, P(S), P(A), P(B), P(F).
    Определим правила для Р2: Р2 = {S → aFb; А → аА; В → aSb; F → bc | bFc}.
    Определим правила для P(S): S => A => B или S =>*А; S=>В, где =>* обозначает
непосредственную выводимость. P(S) = {S → аА; S → aSb).
    Определим правила для Р(А): А => В => S или А =>* В; А => S. Р(А) = {А → aSb; А →
aFb}.
    Определим правила для Р(В): В => S => А или В =>* S; В =>*А. Р(В) = {В → aFb; В →
аА}.
    Определим правила для P(F): так как непосредственно выводимых нетерминалов не
существует, то P(F) = 0.
    Объединив полученные правила, можно записать грамматику Gэ, эквивалентную
исходной:
   S → aFb | aSb | аА;             А → аА | aSb | aFb;
   В → аА | aSb | aFb;             F → bc | bFc.

      Графическая модификация метода
    Аналитическое преобразование по рассмотренному алгоритму оказывается довольно
сложным. При автоматизированном преобразовании грамматик проще применить
графическую модификацию этого метода. С этой целью каждому нетерминальному символу
и каждой правой части правил из множества Р2 поставлена в соответствие вершина графа.
Из вершины с меткой U в вершину с меткой V направлено ребро, если в грамматике
существует правило U → V.
           aFb       aA      aSb bFc          bc




          S       A          B            F