Лекция 3
Определение распознавателя
Второй способ задания формальных языков основан на применении распознавателей [1-3]. Распознаватель - это некоторый алгоритм, который выполняет анализ терминальных цепочек и устанавливает, является ли анализируемая цепочка синтаксически правильной. Если распознаватель выдает ответ - "да", то говорят, что он допускает цепочку и цепочка называется допустимой. Язык, определяемый распознавателем - это множество цепочек, которые он допускает.
Распознаватель можно представить в виде абстрактного устройства, структура которого показана на рис. .
Рис.
Входная лента-это линейная последовательность ячеек, каждая из которых содержит один символ некоторого входного алфавита . Читающая головка в каждый момент обозревает один символ на входной ленте. За один шаг работы распознавателя головка может сдвинуться на одну ячейку вправо, влево или остаться неподвижной. Мы будем рассматривать только односторонние распознаватели, у которых читающая головка никогда не сдвигается влево.
Рабочая память-это некоторое хранилище данных произвольной организации.
Управляющее устройство(УУ) с конечной памятью -основная часть распознавателя, определяющая его поведение.
Работа распознавателя состоит из тактов, а каждый такт из следующих действий:
входная головка сдвигается вправо или остается на месте;
в рабочую память помещается некоторая информация;
изменяется состояние УУ.
Поведение распознавателя удобно описывать в терминах конфигураций. Конфигурацию можно рассматривать как моментальный снимок распознавателя, на котором отражено состояние всех его элементов (состояние УУ, положение читающей головки и др.)
УУ (и сам распознаватель) называется детерминированным, если из текущей конфигурации в результате выполнения такта распознаватель может перейти только в одну очередную конфигурацию, и недетерминированным - если переход возможен в одну из множества конфигураций.
Конечные автоматы. Простейшими из распознавателей являются конечные автоматы(КА).
Определение. КА - это пятерка: ,
где Q- конечное множество состояний КА;
- конечное множество допустимых входных символов (входной алфавит);
- функция переходов (отображение) Q в (Q);
- начальное состояние;
F- множество заключительных состояний.
Функция переходов задает допустимые последовательности переходов КА из одного состояния в другое, в зависимости от читаемых автоматом символов.
Определение. Пара называется конфигурацией КА, при этом конфигурация называется начальной, а ( , e), где F ,- конечной конфигурацией.
Такт работы КА можно представить бинарным отношением , заданным на конфигурациях.
Определение. Определим бинарное отношение следующим
образом:
если для всех a , w *.
Обычным образом вводятся отношения k, *, +,при этом:
запись с 0 означает, что ;
запись с k означает, что существует последовательность конфигураций КА такая, что c i c i+1 для 0 i k-1, т.е. соответствует траектории из k тактов;
запись с * соответствует некоторой траектории КА, переводящей его из , за некоторое число(включая ноль) тактов;
запись соответствует некоторой траектории КА, переводящей его из , за некоторое число k1 тактов.
Говорят, что автомат М допускает цепочку w, если
(q0 , w ) * (q,e) для некоторого qF. Другими словами, цепочка допускается, если существует траектория, переводящая КА из начальной конфигурации в заключительную, в результате выполнения которой эта цепочка оказывается прочитанной.
Языком, определяемым автоматом М, называется множество
цепочек L(M):
L(M)={w | w и (q0 , w ) * (q,e) для некоторого qF }.
Пример 2.14. M=({p,q,r},{0,1}, ,q,{r})
Функцию переходов можно задать в явном виде(в виде функции), в виде таблицы или в виде графа переходов, которые приведены ниже.
В явном виде:
В виде таблицы:
Таблица .
B виде графа переходов (рис. 2.2)
Рис.
При задании КА в виде таблицы на пересечении каждой строки и столбца записывается символ состояния (или множество состояний), в которое переходит автомат из текущего состояния (соответствующего строке), при чтении входного символа (соответствующего столбцу).
При изображении в виде графа, его вершины помечаются состояниями автомата, а дуги — значениями входных символов. Каждая дуга (p,q), помеченная входным символом a, означает, что при чтении a в состоянии p автомат переходит в состояние q. Кроме того, начальное и заключительное состояния выделяют из других состояний КА так, как это показано выше.