Конечные автоматы
Регулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы.
Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q0, F), где



Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт
определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис.3.2).
![]()
|
Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.
Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара (q, w)

справа от него. Конфигурация (q0, w) называется начальной, а конфигурация (q, e), где q

Пусть M = (Q, T, D, q0, F) - НКА. Тактом автомата M называется бинарное отношение






Будем обозначать символом



Говорят, что автомат M допускает цепочку w, если (q0, w)


входных цепочек, допускаемых автоматом M. Т.е.

Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.
Пусть M = (Q, T, D, q0, F) - НКА. Будем называть M детерминированным конечным автоматом (ДКА), если
выполнены следующие два условия:
- D(q, e) = для любого qQ, и
- D(q, a) содержит не более одного элемента для любых q Q и aT.
Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a) = p вместо D(q, a) = {p}.
Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина,
а дуга, помеченная символом a



Пример 3.3. Пусть L = L(r), где r = (a|b)*a(a|b)(a|b).
- Недетерминированный конечный автомат M, допускающий язык L:
где функция переходов D определяется так:M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},
Диаграмма автомата приведена на рис. 3.3, а.D(1, a) = {1, 2}, D(3, a) = {4}, D(2, a) = {3}, D(3, b) = {4}, D(2, b) = {3}. - Детерминированный конечный автомат M, допускающий язык L:
где функция переходов D определяется так:M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}},
Диаграмма автомата приведена на рис. 3.3, б.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.
![]()
|
![]()
|
- При анализе цепочки w = ababa автомат из примера 3.3, а, может сделать следующую последовательность тактов:
(1, ababa)(1, baba)(1, aba)(2, ba)(3, a)(4, e).
Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом. - При анализе цепочки w = ababab автомат из примера 3.3, б, должен сделать следующую последовательность тактов:
(1, ababab)(2, babab)(7, abab)(8, bab)(7, ab)(8, b)(7, e).
Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом.