Автоматы с магазинной памятью. Детерминированные и недетерминированные автоматы с магазинной памятью.
Формально детерминированный магазинный автомат определяется как следующая совокупность объектов:
M = (V, Q, VM, δ, q0, z0, F),
где V, Q, q0 Є Q, F определяются так же, как и для конечного автомата;
VM = {z0, z1,…,zp-1} — алфавит магазинных символов автомата;
δ — функция, отображающая множество Q X (V U { ε }) X VM в множество Q X VM, где е — пустая цепочка;
z0 Є VM — так называемый граничный маркер, т. е. символ, первым появляющийся в магазинной памяти.
Недетерминированный магазинный автомат отличается от детерминированного только тем, что функция δ отображает множество Q X (V U { ε }) X VM. в множество конечных подмножеств Q x VM
Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью наличием выходной ленты.
Далее будем рассматривать только недетерминированные магазинные автоматы.
Рассмотрим интерпретацию функции δ для такого автомата. Эту функцию можно представить совокупностью команд вида
(q, a, z)→(q1, γ1),…,(qm, γm),
где q, q1,…qm Є Q, a Є V, z Є VM, γ1,…,γm Є V*m
При этом считается, что если на входе читающей головки автомата находится символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию qi, записав при этом на рабочую ленту цепочку γi(1 ≤ i ≤ m) вместо символа z, передвинуть входную головку на один символ, и перейти в состояние qi. Крайний левый символ γi должен при этом оказаться в верхней ячейке магазина. Команда (q, e, z)→(q1, γ1),…, (qm, γm) означает, что независимо от входного символа и, не передвигая входной головки, автомат перейдет в состояние qi, заменив символ z магазина на цепочку γi(1 ≤ i ≤ m).
Машина Тьюринга. Устройство машины Тьюринга. Отличия конечного автомата от машины Тьюринга.
Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году.
Машина Тьюринга — отличается от системы с конечным управлением (конечного автомата) только в двух аспектах:
она имеет одну бесконечную рабочую ленту, с которой читает и куда пишет символы,
и одну головку чтения-записи, которая может двигаться по рабочей ленте в любую сторону.
Такая свобода движения головки чтения-записи, по сути, означает возможность создавать и впоследствии анализировать промежуточную информацию любого объема. Как оказывается, такое простое расширение возможностей радикально увеличивает вычислительную мощность машин Тьюринга по сравнению с обычными конечными автоматами.
Устройство машины Тьюринга:
В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной Машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния Машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, и недетерминированной в противном случае.
Конкретная машина Тьюринга задается перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (H)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.