Теория и реализация языков программирования


         

содержит не более одного элемента


Пусть M = (Q, T, D, q0, F) - НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия:

  1. D(q, e) =
    , для любого
    , и
  2. D(q, a) содержит не более одного элемента для любых
    и
    .


Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a)=p вместо D(q, a)={p}.

Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом
соединяет две вершины p и q, если
. На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром).

Пример 3.3. Пусть L = L(r), где r = (a|b)*a(a|b)(a|b).

    1. Недетерминированный конечный автомат M, допускающий язык L:

      M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},

      где функция переходов D определяется так:


      Диаграмма автомата приведена на рис. 3.3 а.
    2. Детерминированный конечный автомат M, допускающий язык L:

      M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}}

      где функция переходов D определяется так:



      Диаграмма автомата приведена на рис. 3.3 б.




Рис. 3.3. 

Пример 3.4. Диаграмма автомата, допускающего множество чисел в десятичной записи, приведена на рис. 3.4.


Рис. 3.4. 

Пример 3.5. Анализ цепочек.

  1. При анализе цепочки w = ababa автомат из примера рис. 3.3, а, может сделать следующую последовательность тактов:


    Состояние 4 является заключительным, отсюда, цепочка w допускается этим автоматом.
  2. При анализе цепочки w = ababab автомат из примера рис. 3.3, б, должен сделать следующую последовательность тактов:


    Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом.



Содержание  Назад  Вперед