Иерархия распознающих автоматов

¨ тип 0 (машина Тьюринга): вспомогательная память представляет собой бесконечную ленту, разделенную на ячейки. В каждую из ячеек может быть записан один символ из заданного конечного множества символов (рабочего алфавита). У автомата имеется головка чтения-записи, которая всегда указывает на одну из ячеек. На каждом шаге можно произвести запись или прочитать, что записано, после чего головка перемещается на одну ячейку вправо или влево, или остается на месте. Говорят, что последовательность символов x Î A * допускается, если машина Тьюринга может быть переведена из некоторого начального состояния в некоторое конечное, причем x последовательными шагами считывается на ввод.

Машину Тьюринга можно рассматривать как механическое устройство, состоящее из следующих основных частей.

1) В машине имеется потенциально неограниченная память, разбитая на отдельные линейно-упорядоченные ячейки. В каждой ячейке может быть записан символ из некоторого конечного алфавита, или же она может быть пустой. В последнем случае часто для удобства считают, что в ячейке записан особый символ, называемый пустым. В каждый момент времени память, называемая рабочей лентой машины, состоит из конечного числа ячеек, однако при необходимости к ней могут быть пристроены слева или справа новые ячейки с записанным в них пустым символом. Итак, рабочая лента и информация, записанная в ней, представляются конечной цепочкой символов над словарем рабочей ленты.

2) Помимо рабочей ленты в машине Тьюринга имеется еще и другое запоминающее устройство. Это регистр состояний – особая память, рассчитанная на хранение одного символа. Символ, который запоминается в регистре, выбирается из конечного множества, определяющего множество состояний машины.

3) В каждый момент времени машина Тьюринга анализирует не всю информацию, хранящуюся на рабочей ленте, а содержимое лишь одной ячейки этой ленты. Для определения этой ячейки служит управляющая головка, которая всегда указывает на некоторую ячейку рабочей ленты.

Выполняя заданный алгоритм, машина Тьюринга последовательно производит ряд элементарных действий, причем каждое такое действие выполняется за один рабочий такт машины. Элементарные действия можно разбить на следующие три группы:

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

2) Машина изменяет состояние и продвигает управляющую головку на одну ячейку влево.

3) Машина изменяет состояние и продвигает управляющую головку на одну ячейку вправо.

Машина Тьюринга может использоваться для вычисления функций, аргументы и значение которых представляются цепочками символов конечных алфавитов. При этом машина начинает работу в так называемой начальной ситуации, которая характеризуется следующим образом:

· на рабочей ленте записан аргумент вычисляемой функции;

· управляющая головка указывает на ячейку, в которой записан самый левый символ аргумента;

· машина находится в некотором заранее выбранном состоянии, которое называется начальным.

Начиная работу с начальной ситуации, машина работает до тех пор, пока не окажется в некотором особом состоянии, называемом заключительным. Значением вычисляемой функции считается цепочка непустых символов, выписанных слева направо из рабочей ленты после окончания работы машины.

Элементарные действия машины Тьюринга определяются функцией

d: A ´ Z ´ Г ® P_f (Z¢ ´ Г¢ ´(–1,0,+1))

где А – принятый символ с вода;

Z – состояние;

Г – символ во вспомогательной памяти, на который указывает головка чтения-записи;

P_f – множество конечных подмножеств;

Z¢ – новое состояние;

Г¢ – новый символ во вспомогательной памяти;

–1 – сдвиг влево головки чтения-записи;

0 – нет сдвига;

+1 – сдвиг вправо.

¨ тип 1 (линейно-ограниченный автомат): сохраняется схема машины Тьюринга и вводится следующие ограничения: при восприятии цепочки символов длины n могут использоваться не более n ячеек вспомогательной памяти.

¨ тип 2 (магазинный автомат): сохраняется схема машины Тьюринга, но при каждом сдвиге влево происходит стирание содержимого ячейки, над которой находилась головка чтения-записи. В результате все ячейки вспомогательной памяти справа от головки затираются.

¨ тип 3 (конечный автомат): вспомогательной памяти нет, так что функция отображения имеет следующий вид d: A ´ Z ® Z. Таким образом, функция отображения автомата определяет, в какое состояние должен быть осуществлен переход исключительно в зависимости от текущего состояния автомата и содержащегося на вводе символа.

В следующих разделах теория формальных языков представлена более полно и распространена на любой язык программирования.