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

    5 Лабораторная работа № 5. Построение автомата с мага-
зинной памятью по контекстно-свободной грамматике

      Цель: - закрепить понятия «автомат с магазинной памятью (МП-
автомат)», «расширенный МП-автомат», «конфигурация МП-автомата»; «стро-
ка и язык, допускаемые МП-автоматом»;
            - сформировать умения и навыки построения МП-автомата и рас-
ширенного МП-автомата по КС-грамматике, разбора входной строки с помо-
щью МП-автомата.
                                       Основы теории
     КС-языки можно распознавать с помощью автомата с магазинной памя-
тью (МП-автомата).
     Определение 5.1. МП-автомат можно представить в виде семерки:

          M = (Q, T , N , F , q0, N 0 , Z ) ,                           (5.1)

     где Q – конечное множество состояний автомата;
         T – конечный входной алфавит;
         N – конечный магазинный алфавит;
         F – магазинная функция, отображающая множество (Q × (T ∪ {ε }) × N )
            во множество всех подмножеств множества Q × N * , т.е.
             F : (Q × (T ∪ {ε }) × N ) → P(Q × N * ) ;
         q0 – начальное состояние автомата, q0 ∈Q;
         N0– начальный символ магазина, N0 ∈ Т;
         Z – множество заключительных состояний автомата, Z ⊆ Q.
     Определение 5.2. Конфигурацией МП-автомата называется тройка вида:

            (q, ω , α ) ∈ (Q × T * × N * ) ,                      (5.2)
     где q - текущее состояние автомата, q ∈ Q;
         ω - часть входной строки, первый символ которой находится под
            входной головкой, ω ∈ T * ;
        α - содержимое магазина, α ∈ N *.




                                                                           27