Обобщенная структура распознавателя

Компоненты распознавателя.

Распознаватели для различных классов грамматик

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

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

2. Входная головка в каждый момент читает одну входную ячейку; за один шаг может сдвинуться на одну ячейку влево или вправо или остаться неподвижной.

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

3. Вспомогательная (рабочая) память хранит информацию, построенную только из символов конечного алфавита памяти; может иметь различную организацию: очередь, стек (магазин) и т. д.

Из вспомогательной памяти можно читать и писать в нее. Для стека и очереди используются специфические операции (вталкивание, выталкивание).

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

4. Устройство управления с конечной памятью – это программа, управляющая поведением распознавателя; может являться аналогом конечного автомата; определяет перемещение входной головки и работу с памятью на каждом шаге (такте); переходит за шаг из одного состояния в другое.

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

Дата добавления: 2014-01-11