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


бравинтон

Конечные автоматы - часть 2


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

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

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

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

a \in T \cup \{e\},
соединяет две вершины p и q, если
p \in D(q, a)
. На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром).

Пример 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 определяется так:

      \begin{align*} & D(1, a) = \{1, 2\}, & D(3, a) = \{4\}, \\ & D(1, b) = \{1\}, & D(2, b) = \{3\}, \\ & D(2, a) = \{3\}, & D(3, b) = \{4\}. \end{align*}

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

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

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

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

      \begin{align*} & D(1, a) = 2, & D(5, a) = 8, \\ & D(1, b) = 1, & D(5, b) = 6, \\ & D(2, a) = 4, & D(6, a) = 2, \\ & D(2, b) = 7, & D(6, b) = 1, \\ & D(3, a) = 3, & D(7, a) = 8, \\ & D(3, b) = 5, & D(7, b) = 6, \\ & D(4, a) = 3, & D(8, a) = 4, \\ & D(4, b) = 5, & D(8, b) = 7. \end{align*}

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


Рис. 3.3. 

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


Рис. 3.4. 

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

  1. При анализе цепочки w = ababa автомат из примера рис. 3.3, а, может сделать следующую последовательность тактов:
    (1, ababa) \vdash (1, baba) \vdash (1, aba) \vdash (2, ba) \vdash (3, a) \vdash (4, e).

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

  2. При анализе цепочки w = ababab автомат из примера рис. 3.3, б, должен сделать следующую последовательность тактов:
    (1, ababab) \vdash (2, babab) \vdash (7, abab) \vdash (8, bab) \vdash (7, ab) \vdash (8, b) \vdash (7, e).

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




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