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

      Определение        5.5.    МП-автомат        с     магазинной       функцией
F : (Q × (T ∪ {ε }) × N * ) → P (Q × N * ) называется расширенным МП-автоматом,
т.е. автоматом, который может заменять цепочку символов конечной длины в
верхушке стека на другую цепочку символов конечной длины.
     Существуют КС-языки, МП-автоматы и расширенные МП-автоматы, оп-
ределяющие один и тот же язык.

           Алгоритм 5.2. Построение МП-автомата по КС-грамматике

      Построим МП-автомат, выполняющий левосторонний разбор. Данный
автомат обладает только одним состоянием и принимает входную строку опус-
тошением магазина. Стек используется для размещения текущей сентенции,
первоначально это начальный символ грамматики. Очередная сентенция полу-
чается заменой верхнего нетерминала стека.
      Вход: КС-грамматика G = (VT , V N , P, S ) .
      Выход: МП-автомат M = (Q, T , N , F , q0 , n0 , Z ) такой, что L(M) = L(G).

      Шаг 1. Положить Q = {q}, q0 = q, Z = ∅, N = VT ∪ VN, T = VT, N0 = S.
        Шаг 2. Для каждого правила вида (А→ β ) ∈ P , где β ∈ V * , сформировать
магазинную функцию вида F (q, ε , A) = (q, β ) . Эти функции предписывают
замещать нетерминал в вершине стека по правилу грамматики.
        Шаг 3. Для каждого t ∈ VT сформировать магазинную функцию вида
F (q, t , t ) = (q, ε ) , которая выталкивает из стека символ, совпадающий с вход-
ным, и перемещает читающую головку. Эти функции обеспечивают опустоше-
ние стека.
      Пример 5.1. Дана КС-грамматика:
      G({+, (, ), a}, {S, A}, {S→S+A | A, A→(S) | a}, {S}). Последовательность
построения МП-автомата будет иметь вид.
      1) Q = {q}, q0 = q, T = {+, (, ), a }, N = {+, (, ), a, S, A}, N0 = S, Z = ∅.
      2) F(q, ε , S) = (q, S+A), F(q, ε , S) = (q, A), F(q, ε , A) = (q, (S));
F(q, ε , A) = (q, a).
      3) F(q, t, t) = (q, ε ) для каждого t ∈{+, (, ), a}.
     Распознавание строки (а) построенным МП-автоматом представлено в
таблице 5.1. Полученный МП-автомат является недетерминированным.




                                                                                    29