Глава 4. Автоматы

§ 4.1. Автоматы: определение, примеры, способы задания

4.1.1 Определение и примеры автоматов

Функционирование автоматического устройства, работающего в дискретном режиме времени по заданному закону (определённому, например, схемой этого устройства), может быть описано на математическом языке с помощью понятия конечного автомата (см. рис. 4.1). В математической теории предполагается, что автомат имеет конечное множество состояний входной алфавит выходной алфавит причём в дискретные моменты времени он принимает входной символ изменяет (или сохраняет) своё состояние и выдаёт на выходе символ Изменение (или сохранение) состояния и символ на выходе автомата зависят от предыдущего состояния и принятого на входе символа

Обозначая через и входной и выходной символы, соответствующие моменту времени мы получим, что автомат перерабатывает входную последовательность в выходную последовательность

Для построения математической теории конечных автоматов необходимо дать строгое определение этому понятию, его мы сейчас приведём.

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

Работа автомата описывается системой канонических уравнений:

которая должна быть дополнена начальным условием Здесь – начальное, или инициальное состояние.

Замечания. 1. Автомат в котором выделено начальное состояние иногда называют инициальным автоматом.

2. Иногда у автомата выделяют одно или несколько состояний (скажем, ), называемых конечными, или финальными состояниями. Смысл их состоит в том, что если автомат “попадёт” в состояние то он прекращает свою работу.

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

4. Многие утверждения, касающиеся автоматов, справедливы и без предположения о том, что – конечные множества. Назовём абстрактным автоматом пятёрку где функции и определяются так же, как и раньше, т.е. но множества могут быть бесконечными.

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

Рассмотрим некоторые примеры автоматов.

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

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

Пример 2. Элемент задержки (см. рис. 4.3). У этого автомата входной и выходной алфавиты совпадают: а выходной символ представляет собой задержанный на 1 такт (на 1 момент времени) входной символ. Таким образом, при всех Построим этот автомат. Пусть В качестве множества состояний возьмём то же множество: Тогда полагаем: Здесь текущее состояние “запоминает” поступившую букву входного алфавита, а выходной буквой является предыдущее состояние, т.е. “запомненная” буква.

Автоматы определённые в этом параграфе, называются автоматами Мили. Определим теперь автомат Мура, или автомат без выхода.

Автоматом Мура называется тройка где – множества, а – отображение.

Множества А и называются соответственно входным алфавитом и множеством состояний. Предполагается, что множества А и конечны, хотя во многих вопросах это не имеет значения. Функция называется функцией переходов. Равенство означает, что если автомат находится в состоянии и принимает символ а, то должен осуществиться его переход в состояние

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

Автомат Мура эквивалентен автомату Мили в том смысле, что “работает” так же, как но реакцией на входной сигнал является не выходной символ а изменённое более сложным образом состояние, в котором фактически “зашифрован” выходной символ