49. Распознаватели
Распознаватель – это очень схематизированный алгоритм, определяющий некоторое множество. Его можно представить в виде устройства (автомата). Этот автомат состоит из трех частей: входной ленты, устройства управления с конечной памятью и вспомогательной (рабочей) памяти (рис 2.3).
Входная лента – линейная последовательность клеток (ячеек), каждая из которых содержит один входной символ из конечного входного алфавита. Могут присутствовать левый и правый концевые маркеры, может присутствовать только один концевой маркер (левый или правый), могут отсутствовать оба маркера.
Входная головка – в каждый момент читает одну входную ячейку. За один шаг входная головка может сдвинуться на одну ячейку влево, вправо и остаться неподвижной.
Распознаватель, никогда не передвигающий входную головку влево, называется односторонним. Обычно предполагается, что входная головка только читает. Но могут быть такие распознаватели, у которых входная головка и читает, и пишет.
Память – хранит информацию, построенную только из символов конечного алфавита памяти. Может иметь различную структуру: очередь, стек (магазин) и т. д. Можно читать из вспомогательной памяти и писать в нее. Для стека и очереди используются специфические операции (вталкивание, выталкивание).
Устройство управления с конечной памятью – программа, управляющая поведением распознавателя. Может являться аналогом конечного автомата. Определяет перемещение входной головки и работу с памятью на каждом шаге (такте). Переходит за шаг из одного состояния в другое.
Конфигурация распознавателя – мгновенный снимок, на котором изображены:
1. состояние устройства управления;
- содержимое входной ленты;
- содержимое памяти.
Начальная конфигурация – устройство управления находится в заданном начальном состоянии, входная головка читает самый левый символ на входной ленте, память имеет заранее установленное начальное содержимое.
Заключительная конфигурация – устройство управления находится в одном из состояний, принадлежащем заранее выделенному множеству заключительных состояний, входная головка обозревает правый концевой маркер или, если маркер отсутствует, сошла с конца входной ленты. Иногда требуется, чтобы заключительная конфигурация памяти удовлетворяла некоторым условиям.
Распознаватель допускает входную цепочку w, если, начиная с начальной конфигурации, в которой цепочка w записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией.
Язык, определяемый распознавателем – это множество цепочек, которые он допускает.
Для каждой из грамматик, приведенных выше в соответствии с иерархией Хомского, существуют распознаватели определяющие один и тот же класс языков.
1. Язык L праволинейный тогда и только тогда, когда он определяется конечным, односторонним детерминированным автоматом.
- Язык L контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью.
- Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно ограниченным автоматом.
- Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга.
Данные определения показывают, что теория языков и формальных грамматик продвинулась достаточно далеко, чтобы служить самостоятельным предметом изучения. Не будем вдаваться в детали и выяснять смысл представленных понятий. Зафиксируем только сам факт эквивалентности между механизмами порождения и распознавания.
| 