НАЧАЛЬНЫЕ ПОНЯТИЯ

КОНЕЧНЫЕ АВТОМАТЫ

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

НАЧАЛЬНЫЕ ПОНЯТИЯ

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

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

Содержательно автомат - это устройство, которое взаимодействует с внешней средой посредством входного и выходного каналов.

Эти каналы называются входом и выходом автомата.

По входному каналу в автомат поступают сигналы из внешней среды.

Через выходной канал автомат выдает во внешнюю среду сигналы, являющиеся результатом его работы.

Автоматы сохраняют информацию о своей предыдущей работе с помощью состояний и используют ее в последующем как данные.

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

Произвольное устройство может считаться автоматом, если оно обладает следующими свойствами:

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

t₀, t₀ + 1, . . . ,t₀ + i, . . . ;

2) в каждый момент времени устройство находится в одном из своих внутренних состояний;

3) сигнал на выходе устройства в некоторый момент времени и его состояние в следующий момент времени однозначно определяются сигналом на входе автомата и его состоянием в текущий момент времени.

Если множество входных сигналов автомата и множество его состояний - конечные, то такой автомат называется конечным автоматом.

Рассмотрим пример реального устройства, которое может считаться конечным автоматом.

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

В качестве входных сигналов устройства можно выбрать:

1) помещение жетона;

2) нажатия на кнопку выбора напитка (количество разных символов равно числу видов имеющихся напитков);

3) пустой сигнал, соответствующий ситуации, когда устройством не пользуются, или состоянию ожидания.

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

Состояния устройства соответствуют ситуациям наличия и отсутствия жетона в приемном кармане.

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