вход Вход Регистрация



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

© 2018
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру