Конечные автоматы. Кодирование информации
Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и т.д.
Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой.
Математической моделью реального КА является абстрактный автомат, который имеет один входной канал и один выходной канал (рис. 4.1):
| X(x1, …, xF) | ---> | A(a0,..., aM) | ---> | Y(y1, …, yG). |
Рис. 4.1. Абстрактный автомат
Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T≠ const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами t = 0, 1, 2, 3, …, имеющими смысл номера такта.
|
|
|
Для задания любого КА S необходимо задавать совокупность из пяти объектов: S{A, X, Y, d, l}, где A = {a0, a1, a2,..., am,..., aM} – множество состояний автомата, X = {x1, x2, …, xf,…, xF} – множество входных сигналов или входной алфавит, Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)], 1 – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)]. Если множества А, Х и У конечны, то автомат называется конечным. Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.
|
|
|
Дата добавления: 2016-01-06; просмотров: 17; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!