Содержательное описание акцептора

На содержательном уровне распознаватель можно представить состоящим из трех частей:

- входной ленты;

- управляющего устройства с конечной памятью;

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

Входная лента

Р и с. 3.2

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

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

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

Рабочей памятью может быть хранилище информации любого типа. Хранящаяся в памяти информация построена из символов алфавита памяти.

Если распознаватель представляет собой конечный акцептор, то он решает задачу распознавания не прибегая к использованию рабочей памяти и работает при этом как односторонний.

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