1. Введение
    В настоящем реферате будут даны определения детермини-
    рованных и недетерминированных конечных автоматов, приведе-
    ны их графы. Далее будет рассмотрен случай преобразования
    недетерминированного конечного автомата в детерминированный
    с рисунками и графами.
    Все рассмотренные здесь автоматы представлены как маши-
    ны, распознающие цепочки символов.
    2. Детерминированные конечные автоматы.
    В различных источниках приводятся несколько отличающие-
    ся друг от друга определения детерминированного конечного
    автомата. Приведем здесь определение из источника [2].
    Детерминированным конечным автоматом (ДКА) называется
    машина, распознающая цепочки символов. Она имеет входную
    ленту, разбитую на клетки, головку на входной ленте (вход-
    ную головку) и управляющее устройство с конечным числом
    состояний (рис. 1). Конечный автомат М можно представить в
    виде пятерки (S, I, 1б 0, 1s0 0, F), где
    1) S - множество состояний 1управляющего устройства 0,
    2) I - 1входной алфавит 0(каждая клетка входной ленты со-
    держит символ из I),
    3) 1б 0 - отображение из S x I в S (если 1б 0( 1s 0, 1a 0) = 1s' 0, то
    всякий раз, когда М находится в состоянии 1s 0, а входная
    головка обозревает символ 1a 0, М сдвигает входную головку
    вправо и переходит в состояние 1 s' 0),
    4) 1 s0 0 - выделенное состояние в S, называемое 1начальным 0,
    5) F - подмножество в S, называемое множеством 1допуска-
    1ющих 0 (или 1 заключительных 0) 1 состояний 0.
    ------T-----T-----¬
    ¦ 1b 0 ¦ 1a 0 ¦ 1c 0 ¦ Входная лента
    L-----+-----+------
    ^
    ¦ Головка
    ---+--¬
    ¦ 1s 0 ¦ Управляющее устройство
    L------
    Рис. 1. Конечный автомат
    ДКА выполняет шаги, определяемые текущим состоянием его
    блока управления и входным символом, обозреваемым входной
    головкой. Каждый шаг состоит из перехода в новое состояние
    и сдвига входной головки на одну клетку вправо. Оказывает-
    ся, что язык представим регулярным [2] выражением тогда и
    только тогда, когда он допускается некоторым конечным авто-
    матом.
    Далее будет приведено определение ДКА через определение
    недетерминированного конечного автомата (НКА), то-есть
    можно будет рассматривать ДКА в качестве подмножества НДКА.
    2. Недетерминированные конечные автоматы
    Для каждого состояния и каждого входного символа НКА
    имеет нуль или более вариантов выбора следующего шага. Он
    может также выбирать, сдвигать ему входную головку при из-
    менении состояния или нет.
    Приведем определение недетерминированного конечного ав-
    томата.
    Недетерминированным конечным автоматом называется пя-
    терка (S, I, 1 б 0, 1 s0 0, F), где
    1) S - конечное множество состояний устройства управле-
    ния;
    2) I - 1 алфавит 0 входных символов;
    3) 1б 0- 1функция переходов 0, отображающая S x (I U { 1e 0}) в
    множество подмножеств множества S;
    4) 1 s0 0 (- S - 1 начальное состояние 0 устройства управления;
    5) F _( .S - множество 1заключительных (допускающих) 0сос-
    тояний.
    С каждым НКА связан ориентированный граф, естественным
    образом представляющий функцию переходов этого автомата.
    Приведем определение для графа ( или диаграммы) перехо-
    дов автомата М = (S, I, 1б 0, 1s0 0, F).
    Графом переходов автомата М называют ориентированный
    граф G = (S, E) с помеченными ребрами. ............