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

                3 Формальная модель задачи

            Определение 1. Детерминированным конечным автоматом (ДКА)
        называется пятерка объектов:

             M = (Q, T , F , H , Z ) ,                                   (2.1)

            где Q - конечное множество состояний автомата;
            T - конечное множество допустимых входных символов;
             F - функция переходов, отображающая множество Q×T во множест-
        во Q;
             H - конечное множество начальных состояний автомата;
            Z - множество заключительных состояний автомата, Z ⊆ Q.
            Определение 2. Недетерминированным конечным автоматом (НКА)
        называется конечный автомат, в котором в качестве функции переходов
        используется отображение Q × T во множество всех подмножеств мно-
        жества состояний автомата P(Q) , т.е. функция переходов неоднозначна,
        так как текущей паре (q, t ) соответствует множество очередных состоя-
        ний автомата q′ ∈ P (Q) .

                    Способы представления функции переходов

                Командный способ. Каждую команду КА записывают в форме
     F (q, t ) = p , где q, p ∈ Q, t ∈ T .
                Табличный способ. Строки таблицы переходов соответствуют
         входным символам автомата t ∈ T, а столбцы – состояниям Q. Ячейки
         таблицы заполняются новыми состояниями, соответствующими значе-
         нию функции F (q, t ) . Неопределенным значениям функции переходов
         соответствуют пустые ячейки таблицы.
                Графический способ. Строится диаграмма состояний автомата –
         неупорядоченный ориентированный помеченный граф. Вершины графа
         помечены именами состояний автомата. Дуга ведет из состояния q в со-
         стояниe p и помечается списком всех символов t ∈ T, для которых
          F (q, t ) = p . Вершина, соответствующая входному состоянию автомата,
         снабжается стрелкой. Заключительное состояние на графе обозначается
         двумя концентрическими окружностями.


                                                                             Лист
                                                                             4


48