Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 36 стр.

    γ - функция выходов, задающая отображение К⋅Х→У.
    Функционирование автомата можно задать множеством команд вида qx → py, где q и p
∈ K, x ∈ X, y ∈ Y.
    Пусть на некотором такте ti управляющее устройство находится в состоянии q, а из
входной ленты читается символ x. Если в множестве команд есть команда qx → py, то на
такте ti на выходную ленту записывается символ y, а к следующему такту ti+1 управляющее
устройство перейдет в состояние p, т.е.:
    y(t) = γ(q(t), x(t)), q(t+1) =δ(q(t), x(t)).
    Если же команда qx → py отсутствует, то автомат оказывается блокированным и не
реагирует на символ, принятый в момент ti, а также перестает воспринимать символы в
последующие моменты времени.
    В соответствии с определением неинициального автомата в начальный момент
состояние автомата может быть произвольным.
    Если зафиксировано некоторое начальное состояние, то такой автомат называют
инициальным, т.е. q(0) = q0.
    Инициальный автомат - это шестерка вида А = (К, X, Y, δ, γ, q0), где
    К - множество состояний (алфавит состояний);
    Х - входной алфавит;
    Y - выходной алфавит;
    δ - функция переходов (отображение К ⋅ Х → К);
    γ - функция выходов (отображение К ⋅ Х → У);
    q0 - начальное состояние.

      5.3. Распознаватели

      5.3.1. Языки и автоматы
    Задача грамматического разбора заключается в нахождении вывода цепочки в заданной
грамматике и определения дерева вывода этой цепочки.
    Языки могут быть заданы двумя способами:
    1) грамматиками (порождающее средство языка);
    2) автоматами (распознающее средство языка).
    Различным по сложности автоматам соответствуют разные типы языков. Простейшим
типом автоматов являются конечные автоматы.
    Конечный автомат имеет входную ленту, с которой за один такт может быть считан один
входной символ. Возврат по входной ленте не допускается.
    Конечным автоматом называется пятерка вида А = (К, ∑, δ, p0, F), где
    К - конечное множество состояний;
    ∑ - алфавит;
    δ - функция переходов;
    p0 - начальное состояние;
    F - множество заключительных состояний.
    Автомат можно определить как формальную систему через состояния, через символы,
которые пишутся (читаются) с ленты или с нескольких лент, и через набор команд.
    Конечный автомат можно представить графом, таблицей переходов, командами, а также
матрицей переходов.

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