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

               N1M = {M , N };
               N 2M = {M , N }.
      Т.к. N1M = N 2M , то N M = {M , N }.

               N 0N = {N };
               N1N = {N }.
      Т.к. N1N = N 0N , то N N = {N }.
      Шаг 2. Преобразовав правила вывода грамматики, получим грамматику
G′ = ({+, n}, {L, M , N }, P′, L) с правилами P′ :
                   1) L → N + | n; 2) M → N + | n; 3) N → N + | n .

            Алгоритм 4.6. Устранение левой факторизации правил
     Вход: КС-грамматика G = (VT , VN , P, S ) .
     Выход: Эквивалентная КС-грамматика G ′ = (VT , V N′ , P′, S ′) без одинако-
вых префиксов в правых частях правил, определяющих нетерминалы.
      Шаг 1. Записать все правила для нетерминала X , имеющие одинаковые
префиксы      α ∈V * , в виде одного                  правила     с    альтернативами:
X → αβ1 | αβ 2 | K | αβ n ; β1, β 2 ,K , β n ∈ V *.
      Шаг 2. Вынести за скобки влево префикс α в каждой строке-
альтернативе: X → α ( β1 | β 2 | K | β n ).
      Шаг 3. Обозначить новым нетерминалом Y выражение, оставшееся в
скобках: X → αY , Y → β1 | β 2 | K | β n .
      Шаг 4. Пополнить множество нетерминалов новым нетерминалом Y и
заменить правила, подвергшиеся факторизации, новыми правилами для X и Y .
      Шаг 5. Повторить шаги 1-4 для всех нетерминалов грамматики, для кото-
рых это возможно и необходимо.
       Пример 4.6. Дана грамматика G = ({k , l , m, n}, {S }, P, S ) с правилами P :
1) S → kSl; 2) S → kSm; 3) S → n . Преобразуем ее в эквивалентную грамма-
тику G′ по алгоритму 4.6:
       Шаг 1. S → kSl | kSm | n .
       Шаг 2. S → kS (l | m) | n .
       Шаг 3,4. Пополнив множество нетерминалов новым нетерминалом С и
заменив правила, подвергшиеся факторизации, получим грамматику
G ′ = ({k , l , m, n}, {S , C}, P′, S ) с правилами P′ : 1) S → kSC ; 2) S → n; 3) C → l ;
4) C → m.



                                                                                       23