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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 7