В начало

Синтез конечных автоматов (Тема)

 

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

 Введем основные понятия и определения.

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

состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

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

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

  Например. В алфавите X = (x₁, x₂), состоящем из двух букв, словами будут: x₁, x₂, x₁x₁, x₁x₂, x₂x₁,x₂x₂, x₁x₁x₁, и т.д.

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

  Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал.

Рис. 1

  Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия  (T = const) и асинхронного действия (T ¹ const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить  целыми не отрицательными натуральными числами, t=0, 1, 2, 3, …., имеющими смысл номера такта.

  Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y, d, d), где

A = {a₀,a₁,a₂,...,a_n} – множество внутренних состояний автомата,

X = {x₁, x₂,…, x_m} – множество входных сигналов (входной алфавит), X_i буква входного алфавита, Y = {y₁, y₂,…, y_k} – множество выходных сигналов (выходной алфавит), 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) = a₀. В момент времени 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 однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.