6.4 Понятие о дискретном (цифровом) автомате

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

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

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

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

2. В асинхронныхЦА моменты переходов из одного состояния в другое заранее неопределенны и могут совершаться через неравные между собой промежутки времени.

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

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

Результат работы ЦА – выдача выходныхсигналов по конечному числувыходныхканалов. При этом число различных выходных сигналов для любого ЦА всегда конечно и каждому отличному от 0 моменту автоматного времени относится соответствующий ему выходной сигнал.

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

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

ЦА, в которых называютсяавтоматамипервогорода, а автоматы, в которых-автоматамивторогорода.

ЦА называется правильным, если выходной сигналопределяется лишь одним его состоянием (или) и не зависит от.

Т.к. состояние в любом ЦА однозначно определяется парой (,), то всякий автомат 2-го рода можно рассматривать как частный случай автоматов 1-го рода. Автоматы 1-го рода называютсяавтоматамиМили.

Правильные автоматы 2-го рода называются автоматамиМура.

Общая теория автоматов разбивается на две большие части: абстрактную теорию автоматов, структурную теорию автоматов.

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

Структурная теория автоматов интересуется прежде всего структурой как самого автомата. Так и его входных и выходных сигналов.

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

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