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

Детерминированные функции

Графическое задание детерминированных функций

Ограниченно-детерминированные функции

8.4 Каноническое уравнение ограниченно-детерминированных функций

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

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

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

Автоматы функционируют в дискретные моменты времени, которые обозначаются натуральными числами t = 0, 1, 2,…. В каждый момент дискретного времени на вход автомата поступает один сигнал (буква), фиксируется определённое состояние автомата и с выхода снимается один сигнал. Реальные автоматы могут иметь, вообще говоря, несколько входов и выходов. В некоторых случаях для решения задач синтеза удобно заменить такие автоматы автоматами с одним входом и одним выходом. Для этого достаточно закодировать соответствующим образом входные и выходные сигналы исходного алфавита. Если, например, автомат имеет два входа, на каждый из которых подаются сигналы 0 или 1, то все возможные комбинации входных сигналов можно закодировать четырьмя буквами

(0, 0), (0, 1), (1, 0), (1, 1).

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