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

Размещено на

Содержание

• Введение
• 1. Синтез конечных автоматов
• 1.1 Основные понятия и определения
• 1.2 Задания конечного автомата
• 2. Элементарные автоматы
• 3. Табличный метод структурного синтеза конечных автоматов
• 3.1 Структурный синтез
• 3.2 Построение синтеза функций возбуждения элементарных автоматов
• 3.3 Комбинационный синтез конечных автоматов
• 4. Тестирование программы
• Выводы
• Список использованных источников
• Приложения

Введение

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

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

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

Для формального описания узлов ЭВМ при их анализе и синтезе используется аппарат алгебры логики. Основные положения алгебры логики разработал в XIX в. английский математик Джордж Буль. Алгебру логики называют также булевой алгеброй.

Логические элементы - устройства, предназначенные для обработки информации в цифровой форме (последовательности сигналов высокого - "1" и низкого - "0" уровней в двоичной логике, последовательность "0", "1" и "2" в троичной логике, последовательности "0", "1", "2", "3", "4", "5", "6", "7", "8"и "9" в десятичной логике).

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

Как правило, триггер имеет два выхода: прямой и инверсный. Число входов зависит от структуры и функций, выполняемых триггером. По способу записи информации триггеры делят на асинхронные и синхронизируемые (тактируемые). В асинхронных триггерах информация может записываться непрерывно и определяется информационными сигналами, действующими на входах в данный момент времени. Если информация заносится в триггер только в момент действия так называемого синхронизирующего сигнала, то такой триггер называют синхронизируемым или тактируемым. Помимо информационных входов тактируемые триггеры имеют тактовый вход синхронизации. В цифровой технике приняты следующие обозначения входов триггеров:

S - раздельный вход установки в единичное состояние (напряжение высокого уровня на прямом выходе Q);

R - раздельный вход установки в нулевое состояние (напряжение низкого уровня на прямом выходе Q);

D - информационный вход (на него подается информация, предназначенная для занесения в триггер);

C - вход синхронизации;

Т - счетный вход.

Наибольшее распространение в цифровых устройствах получили RS-триггер с двумя установочными входами, тактируемый D-триггер и счетный Т-триггер.

Регистр - последовательное логическое устройство, используемое для хранения n-разрядных двоичных слов (чисел) и выполнения преобразований над ними.

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

Фактически любое цифровое устройство можно представить в виде совокупности регистров, соединённых друг с другом при помощи комбинационных цифровых устройств.

Основой построения регистров являются D-триггеры, RS-триггеры.

конечный автомат комбинационный синтез

1. Синтез конечных автоматов

1.1 Основные понятия и определения

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

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

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

Например. В алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1, и т.д.

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

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

. >A (a0,a1,an) >

X y (y1,y2,…,yk)

Рисунок 1.1 - абстрактная модель автомата

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

1.2 Задания конечного автомата

Для задания конечного автомата 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 букв тоже совпадут.

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