МПС
Синтез
конечных автоматов (Тема) В
комбинационных схемах выходные сигналы
однозначно определяются входными сигналами и не зависят от входных сигналов в
предшествующие моменты времени. Сейчас мы приступаем к изучению второго
большого класса схем ЦВМ, которые содержат в своем составе элементы памяти
(запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или
просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не
только от значения входных сигналов в тот же момент времени, но и от состояния
схемы, которое, в свою очередь, определяется значениями входных сигналов,
поступивших в предшествующие моменты
времени. Введем основные понятия и определения. Автоматом
называется дискретный преобразователь информации, способный принимать различные
состояния, переходить под воздействием входных сигналов из одного состояния в
другое и выдавать выходные сигналы. Если множество состояний
автомата, а так же множества входных и выходных сигналов конечны, то автомат
называется конечным автоматом. Понятие состояния введено в связи с тем, что
часто возникает необходимость в описании поведения систем, выходные сигналы
которых зависят не только от состояния входов в данный момент времени, но и от
некоторых предысторий, т.е. от сигналов, которые поступали на входы системы
ранее. Состояния как раз и соответствуют
некоторой памяти о прошлом, позволяя устранить время как явную
переменную и выразить выходные сигналы как функцию состояний и входов в данный
момент времени. Информацию, поступающую на вход автомата, а
так же выходную информацию принято кодировать конечной совокупностью символов.
Эту совокупность называют алфавитом,
отдельные символы, образующие алфавит – буквами,
а любые упорядоченные последовательности букв данного алфавита – словами в этом алфавите. Например. В алфавите X = (x1, x2),
состоящем из двух букв, словами будут: x1, x2, x1x1,
x1x2, x2x1,x2x2,
x1x1x1, и т.д. Наряду со словами, состоящими не менее чем из
одной буквы, введем слово, не содержащее ни одной буквы, которую будем обозначать
символом е и называть пустым словом или пустой буквой. Математической моделью реального конечного
автомата является абстрактный автомат, который имеет один входной канал и один
выходной канал. Рис. 1 Автомат функционирует в дискретные моменты
времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход
автомата поступает одна буква входного алфавита, автомат переходит из одного
состояния в другое и выдается одна буква выходного алфавита. В зависимости от
того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T ¹ const). Мы будем
рассматривать, в основном, синхронные автоматы, функционирующие в дискретные
моменты времени, которые можно обозначить
целыми не отрицательными натуральными числами, t=0, 1, 2, 3, ….,
имеющими смысл номера такта. Для
задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y, d, d),
где A = {a0,a1,a2,...,an}
– множество внутренних состояний автомата, X = {x1,
x2,…, xm} – множество входных сигналов (входной алфавит),
Xi буква входного алфавита, Y = {y1, y2,…, yk}
– множество выходных сигналов (выходной алфавит), d - функция переходов,
определяющая состояние автомата a(t+1), в котором автомат будет находиться в
момент времени (t+1), в зависимости от состояния автомата a(t) и входного
сигнала x(t) в момент времени t, т.е.
a(t+1) = d
[a(t),x(t)], l
- функция выходов, определяющая значение выходного сигнала y(t) в зависимости
от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = l[a(t),
x(t)]. Автомат работает следующим образом: в каждый момент времени t он
находится в определенном состоянии a(t) из множества А возможных состояний, причем
в начальный момент времени t = 0, он всегда находится в состоянии a(t = 0) = a0.
В момент времени t автомат воспринимает входной сигнал 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). Такие автоматы называют детерминированными. Преобразование
информации в детерминированных автоматах подчиняется следующим условиям: 1. Любое входное
слово длинною l букв, преобразуется в выходное слово той же длины. 2. Если каждый раз перед подачей входных сигналов
автомат находится в одном и том же состоянии, то при совпадении в двух входных
словах первых l1 букв, в выходных словах первые l1 букв тоже совпадут. Кроме детерминированных автоматов существуют вероятностные или стохастические
автоматы, в которых переход из одного состояния в другое под воздействием
случайных или детерминированных входных сигналов происходит случайно. Работа
таких автоматов описывается уже матрицей переходов d, элементами которой
являются вероятности переходов из одного состояния в другое. Мы
будем изучать детерминированные автоматы. Применяемые на практике автоматы принято
разделять на два класса: - это автоматы
Мили и автоматы Мура, названные
так по имени американских ученых, которые впервые начали их изучать. Закон функционирования автоматов Мили
описывается следующей системой уравнений: a(t + 1) = d[a(t),x(t)] ü y(t) = l[a(t),x(t)] ý . t = 0,1,2,3… þ Работа
автоматов Мура задается следующими уравнениями: a(t + 1) = d[a(t),x(t)] ü ý. y(t) = l[a(t)] þ Отличительной
особенностью автоматов Мили является то, что их выходные сигналы зависят как от
состояния автомата, так и от значения входного сигнала. В автоматах Мура
выходные сигналы y(t) в каждый дискретный момент времени t однозначно
определяются состоянием автомата в тот же момент времени и не зависят от
значения входного сигнала. |
||