Конечные автоматы

Регулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы.

Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q0, F), где

Q - конечное множество состояний;

T - конечное множество допустимых входных символов (входной алфавит);

D - функция переходов (отображающая множество QЧ(T

{e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;

q0

Q - начальное состояние управляющего устройства;

F

Q - множество заключительных состояний.

Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт

определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис.3.2).

Рис. 3.2:

Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.

Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара (q, w)

QЧT*, где q - текущее состояние управляющего устройства, а w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов

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

F - заключительной (или допускающей).

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

, определенное на конфигурациях M следующим образом: если p D(q, a), где a T {e}, то (q, aw) (p, w) для всех w T*.

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

+ (*) транзитивное (рефлексивно- транзитивное) замыкание отношения .

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

*(q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество

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



Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.

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

выполнены следующие два условия:

• D(q, e) =
  
  для любого q
  
  Q, и



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

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

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

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

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

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

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

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

  	D(1, a) = {1, 2},	D(3, a) = {4},
  	D(2, a) = {3},	D(3, b) = {4},
  	D(2, b) = {3}.

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



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

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

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

  	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.

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

Рис. 3.3:

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

Рис. 3.4:

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

• При анализе цепочки 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 не допускается этим автоматом.

Содержание раздела

---