Лекция 2 Конечные автоматы Автоматы
Автомат можно рассматривать как упрощенную абстрактную модель компьютера. Он имеет способность воспринимать входную информацию, которую мы будем представлять в виде строки символов в фиксированном алфавите и которую автомат может лишь читать, но не может изменять. Предполагается, что входная строка записана на ленте, разделенной на клеточки, каждая из которых может содержать не более одного символа. Автомат может различать конец входной строки (например, отмеченный специальным символом) и реагировать на прочитанную информацию тем или иным способом. У него может быть устройство временной памяти, содержащее потенциально неограниченное число ячеек, в каждую из которых может быть записано не более одного символа из некоторого алфавита (вообще говоря, не совпадающего с входным). Автомат может читать и изменять содержимое ячеек временной памяти. Наконец, автомат имеет устройство управления, которое может находиться в одном из конечного множества внутренних состояний и изменять его по мере необходимости.
Свойства автомата самым существенным образом зависят от характера временной памяти. Предполагается, что автомат функционирует в дискретном времени. В каждый момент времени устройство управления находится в некотором внутреннем состоянии, а читающая головка обозревает очередной символ на входной ленте. В следующий момент времени устройство управления переходит в некоторое новое состояние в зависимости от предыдущего состояния, прочитанного символа на входной ленте и содержимого временной памяти.
Устройство
Выход Временная
управления память
Читающая
головка
a a b b Входная лента
Направление чтения
Рис. 2.1. Схема автомата
Это соответствие задает функцию перехода автомата, которая определяет его возможное поведение. В результате перехода автомата из одного состояния в другое может появиться выходная информация или может быть записана новая информация во временную память.
Состояние устройства управления, прочитанный входной символ и содержимое временной памяти определяют то, что называется конфигурацией автомата в данный момент времени. Переход от одной конфигурации в момент времени t к другой конфигурации в момент t + 1 называется шагом. Таким образом, функционирование автомата состоит из последовательности шагов (конечной или бесконечной). Различают два типа автоматов: детерминированные и недетерминированные. Поведение детерминированного автомата в каждый следующий момент времени полностью предопределено его внутренним состоянием в предыдущий момент, прочитанным символом и содержимым временной памяти, т.е. если автомат может совершить следующий шаг, то он будет единственно возможным шагом. Для недетер-минированного автомата это не так: в каждый следующий момент времени автомат может выбрать шаг из некоторого (конечного) множества шагов. Таким образом, для недетерминированного автомата мы можем лишь предполагать тот или иной возможный вариант функционирования. Между детерминированными и недетерминированными автоматами существуют интересные с точки зрения формальных языков связи.
Автомат, выход которого ограничен двумя сообщениями {да, нет}, называется распознавателем. Реагируя на входную строку, распознаватель или распознает ее (допускает), или отвергает. Этот класс автоматов представляет наибольший интерес с точки зрения формальных языков и грамматик. Автомат более общего типа, выдающий на выходе целую строку символов, называется преобразователем (этот тип автоматов не изучается в нашем курсе).
Пример 2.1.
Рассмотрим грамматику GI , порождающую подъязык идентификаторов LI в языке Паскаль:
GI: <идентификатор> <буква> <хвост> ,
<хвост > <буква> <хвост> | <цифра> <хвост> | ,
<буква> a | b | c | ... | A | B | ... | Z
<цифра> 0 | 1 | 2 | ... | 9 .
Здесь N = {<идентификатор>, <буква>, <цифра>, <хвост>},
T = {a, b, ..., A, B, ..., Z, 0, 1, 2, ..., 9, }, S = <идентификатор>.
Вывод идентификатора А1 выглядит так:
<идентификатор><буква><хвост>A<хвост>A<цифра><хвост> A<цифра> A1.
Построим автомат, распознающий только язык LI и никакой другой:
Пуск
буква буква
Да или
цифра
цифра
Нет
буква
или
цифра
Рис. 2.2. Автомат, распознающий язык LI