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

    2 Лабораторная работа № 2. Тема: «Построение конечного
автомата по регулярной грамматике»

      Цель: - закрепить понятия «регулярная грамматика», «недетерминиро-
ванный и детерминированный конечный автомат»;
            - сформировать умения и навыки построения конечного автомата
по регулярной грамматике и преобразования недетерминированного конечного
автомата к детерминированному конечному автомату.
                                         Основы теории
        Распознавателем для регулярной грамматики является конечный автомат
(КА).
     Определение 2.1. Детерминированным конечным автоматом (ДКА) на-
зывается пятерка объектов:

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

      где Q - конечное множество состояний автомата;
             T - конечное множество допустимых входных символов;
             F - функция переходов, отображающая множество Q × T во множест-
                  во Q;
             H - конечное множество начальных состояний автомата;
             Z - множество заключительных состояний автомата, Z ⊆ Q.
      Определение 2.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 . Вершина, соот-
ветствующая входному состоянию автомата, снабжается стрелкой. Заключи-

8