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

      Таблица 7.2 – Матрица предшествования символов грамматики
 Символы        S          R           a         (          )           ⊥к
    S                                 =⋅
    R                                 ⋅>                                ⋅>
    a                                 ⋅>                    =⋅          ⋅>
    (           <⋅         =⋅         <⋅         <⋅
    )                                 ⋅>                                ⋅>
   ⊥н                                 <⋅         <⋅
      Шаг 3. Функционирование распознавателя для цепочки (((aa)a)a) показа-
но в таблице 7.3.
      Таблица 7.3 – Алгоритм работы распознавателя цепочки (((aa)a)a)
Шаг           Стек              Входной буфер               Действие
 1         ⊥н                    (((aa)a)a)⊥к              сдвиг
 2         ⊥н(                   ((aa)a)a)⊥к               cдвиг
 3         ⊥н((                  (aa)a)a)⊥к                cдвиг
 4         ⊥н(((                 aa)a)a)⊥к                 cдвиг
 5         ⊥н(((a                a)a)a)⊥к                  свертка S→a
 6         ⊥н(((S                a)a)a)⊥к                  сдвиг
 7         ⊥н(((Sa               )a)a)⊥к                   сдвиг
 8         ⊥н(((Sa)              a)a)⊥к                    свертка R→Sa)
 9         ⊥н(((R                a)a)⊥к                    свертка S→(R
10         ⊥н((S                 a)a)⊥к                    сдвиг
11         ⊥н((Sa                )a)⊥к                     сдвиг
12         ⊥н((Sa)               a)⊥к                      свертка R→Sa)
13         ⊥н((R                 a)⊥к                      свертка S→(R
14         ⊥н(S                  a)⊥к                      сдвиг
15         ⊥н(Sa                 )⊥к                       сдвиг
16         ⊥н(Sa)                ⊥к                        свертка R→Sa)
17         ⊥н(R                  ⊥к                        свертка S→(R
18         ⊥нS                   ⊥к                        строка принята

      Шаг 4. Получили следующую цепочку вывода:
      S⇒(R⇒(Sa)⇒((Ra)⇒((Sa)a)⇒(((Ra)a)⇒(((Sa)a)a)⇒(((aa)a)a).




42