Конечные автоматы и преобразователи

Распознающие автоматы
Входная очередь
Устройство управления с конечной памятью
Вспомогательная память
Линейная последовательность символов из Σ.
За один такт считывается один символ.
Поддерживает функции доступа к памяти
и преобразования памяти (например, замена символа в вершине стека на цепочку).
Множество состояний и отображение, описывающее переход к следующему состоянию в зависимости от текущего входного символа и данных из вспомогательной памяти
Распознаватель допускает входную цепочку w, если, начиная с начальной конфигурации, в которой w записана во входной очереди, распознаватель может выполнить последовательность тактов, завершающуюся конечной конфигурацией.

Конечный автомат
Входная очередь
Устройство управления с конечной памятью
Недетерминированный конечный автомат – пятерка объектов: К=(Q, Σ, δ, q0, F)
Q – множество состояний УУ,
Σ – алфавит входных символов,
δ: Q× Σ→P(Q) – функция переходов,
q0 – начальное состояние,
F – множество заключительных состояний

Конечные преобразователи
Входная очередь
Устройство управления с конечной памятью
Выходная очередь
Такт работы конечного преобразователя – переход от конфигурации (q, ax, y) к конфигурации (r, x, yz), если δ(q,a) содержит (r, z).

Автомат с магазинной памятью
Входная очередь
Устройство управления с конечной памятью
γ
α
Z0
стек
Такт работы МП-автомата:
переход от конфигурации (q, aw, Z) к конфигурации (r, w, γα), если δ(q, a, Z) содержит (r, γ).