Схема работы распознавателя

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

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

Управляющее устройство – это программа управления распознавателем. Она задает конечное множество состояний распознавателя и определяет переходы из состояния в состояние в зависимости от прочитанного символа входной ленты и содержимого вспомогательной памяти.

Вспомогательная память служит для хранения информации, которая зависит от состояния распознавателя. У некоторых типов распознавателей она может отсутствовать.

а₁ а₂ … а_n Входная лента

Рисунок 1.4 – Схема распознавателя

Поведение распознавателя можно представить с помощью его конфигураций.

ОпределениеКонфигурация распознавателя есть совокупность следующих элементов:

- состояние управляющего устройства;

- содержимое входной ленты и положение входной головки;

- содержимое вспомогательной памяти.

ОпределениеУправляющее устройство называется детерминированным, если для каждой конфигурации распознавателя существует не более одного возможного следующего шага, в противном случае управляющее устройство называется недетерминированным.

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

ОпределениеКонфигурация распознавателя называется заключительной, если управляющее устройство находится в одном из заранее выделенных заключительных состояний, а входная головка сошла с правого конца входной ленты. Содержимое вспомогательной памяти удовлетворяет некоторому установленному условию.

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

ОпределениеМножество всех строк, допускаемых распознавателем, называется языком распознавателя.