Определение абстрактного цифрового автомата

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

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

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

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

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

Например, в алфавите , состоящем из двух букв, словами будут: , , , , , , и т.д.

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

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

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

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

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

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

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

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

Преобразование информации в детерминированных автоматах подчиняется следующим условиям:

1. любое входное слово длиною букв, преобразуется автоматом в выходное слово той же длины ;

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

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

Мы будем рассматривать здесь только детерминированные автоматы.

Применяемые на практике автоматы принято разделять на два класса: – это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.

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

,

(3.1)

а работа автомата Мура задается уравнениями вида

(3.2)

где .

Из уравнений (3.1) и (3.2), которые часто называют законами функционирования, видно, что отличительной особенностью автомата Мили является то, что его выходные сигналы зависят как от состояния автомата, так и от значений входного сигнала. У автомата Мура выходные сигналы в каждый дискретный момент времени однозначно определяются состоянием автомата в тот же самый момент времени и не зависят от входного сигнала. Следовательно, для полного задания автомата Мили или Мура дополнительно к законам функционирования необходимо указать начальное состояние и определить внутренний, входной и выходной алфавиты. Существует несколько способов задания работы автомата, но наиболее часто используются табличный, графический и матричный способы [5].

Дата добавления: 2015-07-08