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

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

Распознаватель состоит из трех частей – входной ленты, управляющего устройства с конечной памятью и вспомогательной, или рабочей, памяти. -Входная лента – последовательность клеток, иди ячеек, причем каждая ячейка содержит точно один входной символ из некоторого конечного входного алфавита. Самую левую и самую правую ячейки могут занимать особые концевые маркеры; маркер может стоять только на правом конце ленты; маркеров может не быть совсем. Входная головка в каждый данный момент читает одну ячейку. За один шаг работы распознавателя входная головка может сдвинуться на одну ячейку влево, остаться неподвижной или сдвинуться на одну ячейку вправо. Распознаватель, который никогда не передвигает свою входную головку влево, называется односторонним. - Могут быть и такие распознаватели, у которых входная головка читает и пишет.Памятью распознавателя может быть любого типа хранилище информации, или данных. -Предполагается, что алфавит памяти конечен и хранящаяся в памяти информация построена только из символов этого алфавита. Предполагается также, что в любой момент времени можно конечными средствами описать содержимое и структуру памяти, хотя с течением времени объем памяти может становиться сколь угодно большим. Важный пример вспомогательной памяти – магазинная память. Поведение вспомогательной памяти для заданного класса распознавателей можно охарактеризовать с помощью двух функций: функции доступа к памяти – это отображение множества возможных состояний памяти в конечное множество информационных символов, которое может совпадать с алфавитом памяти.

Функция преобразования памяти- это отображение, описывающее изменения памяти. Она отображает состояние памяти и управляющую цепочку в состояние памяти. Именно тип памяти определяет название распознавателя. Например, распознаватель, память которого организована как магазин, можно назвать распознавателем с магазинной памятью. Ядром распознавателя является управляющее устройство с конечной памятью, под которым можно понимать программу, управляющую поведением распознавателя. Поведение распознавателя удобно описывать в терминах конфигураций распознавателя. -Конфигурация – это как бы мгновенный снимок распознавателя, на котором изображены:

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

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

• содержимое памяти.

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

Для каждого класса грамматик из иерархии Хомского существует класс распознавателей, определяющий тот же класс языков. Этим распознавателями являются конечные автоматы, автоматы с магазинной памятью, линейно ограниченные автоматы и машины Тьюринга. Точнее, языки из иерархии Хомского можно охарактеризовать так: -Язык L праволинейный тогда и только тогда, когда он определяется (односторонним детерминированным) конечным автоматом. -Язык L контекстно-свободный тогда и только тогда, когда он определяется (односторонним недетерминированным) автоматом с магазинной памятью. - Язык L контекстно-зависимый тогда и только тогда, когда он определяется (двусторонним недетерминированным) линейно ограниченным автоматом.

Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга.