Теория автоматов

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

В данном разделе рассматриваются абстрактные автоматы, т.е. некоторая математическая модель. Вопросы практической реализации не рассматриваются. В связи с этим при построении автоматов будем иметь в виду, что:

1. Автомат функционирует в абстрактном времени.

2. Все переходы происходят мгновенно.

Автомат представляет собой кортеж 6 –го порядка:

, (5.1)

где – множество входных сигналов (входной алфавит),

– множество выходных сигналов (выходной алфавит),

– множество внутренних состояний,

– функция перехода,

– функция выхода,

- начальное состояние автомата.