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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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