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

      2) F(q, ε , S+A) = (q, S), F(q, ε , A) = (q, S), F(q, ε , (S)) = (q, A),
F(q, ε , a) = (q, A).
      3) F(q, t, ε ) = (q, t) для каждого t ∈{+, (, ), a}.
      4) F(q, ε , #S) = (r, ε ).
     Распознавание строки (а) расширенным МП-автоматом представлено в
таблице 5.2. Полученный МП-автомат является детерминированным.

     Таблица 5.2 – Распознавание расширенным МП-автоматом строки (а)

   Номер          Текущее
                                Входная строка        Содержимое магазина
конфигурации     состояние
     1               q                (a)                        #
     2               q                a)                        #(
     3               q                 )                       #(a
     4               q                 )                       #(A
     5               q                 )                       #(S
     6               q                 ε                       #(S)
     7               q                 ε                        #A
     8               q                 ε                        #S
     9               r                 ε                        ε

                 Постановка задачи к лабораторной работе № 5
      Разработать программное средство, реализующее следующие функции:
      а) ввод произвольной формальной грамматики и проверка ее на принад-
лежность к классу КС-грамматик;
      б) построение МП-автомата по КС-грамматике;
      в) построение расширенного МП-автомата по КС-грамматике.
      Продемонстрировать разбор некоторой входной строки с помощью по-
строенных автоматов для случая:
      а) входная строка принадлежит языку исходной КС-грамматики и допус-
кается МП-автоматом;
      б) входная строка не принадлежит языку исходной КС-грамматики и не
принимается МП-автоматом.
      Индивидуальные варианты заданий представлены в таблице 4.1.




                                                                            31