Распознаватели и автоматы

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

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

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

Внешняя память распознавателя - это хранилище информации (данных) некоторого типа. Алфавит памяти Z конечен и информация в памяти образована только из символов этого алфавита. Предполагается, что в любой момент времени можно конечными средствами описать содержимое и структуру памяти, хотя с течением времени и работы распознавателя, объем памяти может становиться сколь угодно большим.

Поведение вспомогательной памяти для заданного класса распознавателей можно охарактеризовать с помощью двух функций: функции доступа к памяти (ФДП) и функции преобразования памяти (ФПП).

ФДП - это отображение множества состояний (конфигураций) памяти в конечное множество информационных символов, которое может совпадать с алфавитом памяти. Например, единственная информация доступная в каждый данный момент в магазине (стеке) - верхний символ магазина. Таким образом функция доступа к магазинной памяти f - это такое отображение Z ^* в Z, где Z - алфавит памяти, что

f(z₁z₂...z_n) = z₁,

где z _i Î Z для всех

ФПП - это отображение, описывающее изменение памяти. Она отображает состояние памяти и управляющую цепочку в состояние памяти. Если предполагается, что операция над магазинной памятью заменяет верхний символ конечной цепочкой символов памяти, то соответствующую ФПП можно определить как такое отображение g: Z ⁺ ´Z ^* ® Z ^*, что

g(z₁z₂...z_n,x₁x₂...x_m) = x₁x₂...x_mz₂...z_n,

где z _i , x _j Î Z для всех и . Если верхний символ магазина z₁ заменяется пустой цепочкой, то z₂ станет верхним символом магазина.

Вообще именно тип внешней памяти определяет название распознавателя. Например, распознаватель, память которого организована как магазин, называется распознавателем с магазинной памятью. (Обычно его называют автоматом с магазинной памятью или МП-автоматом.)

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

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

(1) входная головка сдвигается на одну ячейку вправо, влево или сохраняет исходное положение;

(2) в память помещается некоторая информация;

(3) изменяется состояние управляющего устройства.

Поведение распознавателя удобно описывать в терминах конфигурации - мгновенного снимка распознавателя, на котором изображены:

(1) состояние устройства;

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

(3) содержимое памяти.

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

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

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

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

Язык, определяемый распознавателем - это множество входных цепочек, которые он допускает.

Для каждого класса грамматик в иерархии Хомского существует естественный класс распознавателей, определяющий тот же класс языков. Справедливы следующие утверждения:

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

Язык L контекстно свободный тогда и только тогда, когда он определяется односторонним недетерминированным МП - автоматом.

Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно-ограниченным (ЛО-) автоматом.

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

Заметим, что все интересующие нас распознаватели называются автоматами и неслучайно термин автомат вынесен в название данного раздела и всего пособия.

Дата добавления: 2015-06-27