Определение абстрактного цифрового автомата

Математической моделью дискретного устройства является абстрактный автомат, определяемый как шестикомпонентный вектор (или кортеж)

S =< A, X, Y, d, l, a ₁>.

1. А = { a ₁, …, a _m, … a _M} – множество состояний (алфавит внутренних состояний).

2. Х = { x ₁, …, x _f, … x _F} – множество входных состояний (входной алфавит).

3. Y = { y ₁, …, y _g, … y _G} – множество выходных состояний (выходной алфавит).

4. Функция d: А×Х→А – функция переходов, реализующую сюрьективное отображение d: А×Х на А. Другими словами, функция d некоторым парам «состояние – входной сигнал» (a _m, x _f) ставит в соответствие состояния автомата a _s = d (a _m, x _f), a _sÎ А.

5. Функция l: A×X®Y – функция выходов, реализующая сюрьективное отображение l: A×X на Y. Функция l некоторым парам «состояние - входной сигнал» (a _m, x _f) ставит в соответствие выходные сигналы автомата y _g = l (a _m, x _f).

6. a ₁Î A – начальное состояние автомата.

Определения.

Соответствие G Í A×B это подмножество декартова произведения A×B, где A – множество отправления, а B – множество прибытия.

Соответствие называется всюду определенным, если область определения совпадает со множеством отправления.

Соответствие называется сюрьективным, если область значения совпадает со множеством прибытия.

Образом элемента а в В при соответствии G называется множество всех элементов b Î B, соответствующих элементу a Î А.

Прообразом элемента b в A при соответствии G называется множество всех элементов a Î А, соответствующих элементу b Î B.

Соответствие называется инъективным тогда, когда прообразом любого элемента из области значения является единственный элемент из области определения.

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

Биективное или взаимнооднозначное соответствие – соответствие, которое является всюду определенным, сюрьективным, инъективным и функциональным.

Функциональное соответствие (функция) из A в B – соответствие, при котором каждому элементу из области определения соответствует единственный элемент из области значения.

Полностью определенная функция из A в B называется отображением A в B.

Если функциональное соответствие (функция) из A в B сюрьективно, то есть любой элемент из B имеет прообраз в A, имеет место сюрьективное отображение, т.е. отображение A на B.

Под алфавитом понимается непустое множество попарно различных символов.

Элементы алфавита называются буквами.

Конечная упорядоченная последовательность букв называется словом в данном алфавите. Из рассмотрения не исключается и пустая последовательность букв (последовательность нулевой длины) – пустое слово, которое будем обозначать буквой e или Х ₀.

Абстрактный цифровой автомат (рис.4.1) имеет один вход X и один выход Y. Автомат функционирует в дискретном времени, принимающим целые неотрицательные значения t =0, 1, 2,…. В каждый момент t дискретного времени дискретный автомат (ДА) находится в некотором состоянии a (t) из множества внутренних состояний А, причем, в начальный момент t =0 он всегда находится в начальном состоянии a (0)= a ₁. В момент времени t, будучи в состоянии a (t), автомат способен воспринимать на входе букву входного алфавита X (t) Î X. В соответствии с функцией выходов он выдает в тот же момент времени t на выходе букву выходного алфавита y (t)= l [ a (t), x (t)] и в соответствии с функцией переходов d переходит в следующее состояние a (t +1)= d [ a (t), x (t)], a (t) Î A, y (t) Î Y.

Рисунок 4.1 – Абстрактный автомат

Смысл понятия абстрактного цифрового автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Х в множество слов выходного алфавита Y, иначе, если на вход автомата, установленного в начальное состояние a ₁ подавать буква за буквой некоторую последовательность букв входного алфавита x (0), x (1), x (2),… – входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита – y (0), y (1), y (2),… – выходное слово.

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

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

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

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

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

Известен также класс автоматов, у которых выход не зависит от предыстории и в каждый данный момент определяется лишь входным сигналом в этот же момент времени – это так называемые комбинационные схемы или примитивные автоматы без памяти. Примитивный автомат может быть описан тройкой d = (X, Y, l), где X, Y – входной и выходной алфавиты соответственно, а l: X®Y – функция выходов.

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

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