Понятие о дискретном автомате и его математическое описание | MegaDOCs

Понятие о дискретном автомате и его математическое описание

5

ТЕМА 1 Основы алгебры логики и логических функций ЛЕКЦИЯ 1 Введение. Понятие о дискретном автомате и его математическое описание

Вопросы лекции:
  1.  Предмет, цель и задачи курса.

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

Понятие о дискретном автомате.

Понятие о математическом описании дискретных автоматов

Литература: 

1. Математическая энциклопедия. Ред. коллегия: И.М. Виноградов и др. Т.1 – М.: Советская энциклопедия, 1977 г.

3. Понятие о дискретном автомате. Понятие о математическом описании дискретных автоматов

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

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

Рассмотрим основные понятия, относящиеся к дискретным автоматам.

Теория автоматов1 – раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации.

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

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

Понятие конечного автомата возникло в 40-50-х годах 20 века в связи с попытками описать функционирование нервных систем, универсальных вычислительных машин и других реальных управляющих систем. К первым работам относятся публикации У. Мак-Каллака и У. Питтса (1943), С. К. Клини (1951), А.Беркса и Дж. Райта (1954). С 1945 по 1949 гг. публикуется ряд статей советского ученого М. А. Гаврилова, посвященных отдельным вопросам теории релейных устройств. Большой вклад в развитие теории автоматов внесли отечественные ученые школы академика В.М. Глушкова.

 

Рис. 1.1 Обобщенная структурная схема дискретного автомата

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

Иногда автоматы называют дискретными (цифровыми)  автоматами, так как они функционируют в дискретной время и осуществляют преобразование дискретной информации.

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

В теории автоматов переходные процессы не учитываются – вводят абстрактные моменты времени  нумерующие границы тактов. Считается, что процесс, относящийся к такту  (подача воздействия, изменение состояния, выдача выходного воздействия) происходят мгновенно.

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

То есть такая информация является дискретной информацией.

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

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

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

4. Понятие о математическом описании дискретных автоматов

Существуют два подхода к определению дискретного автомата - макроподход и микроподход.

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

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

 

Рис. 1.2 Структурная схема дискретного автомата

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

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

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

Поведение автомата - математическое понятие, описывающее взаимодействие автомата с внешней средой.

В зависимости от типа поведения дискретные автоматы подразделяются на преобразователи, рецепторы (распознаватели) и генераторы.

Для определения поведения автомата функции перехода и выхода распространяют на множество , где  - множество всех слов входного алфавита, включая пустое слово :

;

.

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

Введем обозначение начальной части слова  длиной  как , и слов в алфавитах  и  -  и , определяемые как:

;

.

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

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

.

Автомат с выделенным начальным состоянием называется инициальным и обозначается .

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

Для инициального автомата-акцептора подмножество входного множества , определенное для выделенного подмножества заключительных состояний автомата , определяется как

.

Классификация дискретных устройств

По объему памяти. Устройства описываются моделями

  •  без памяти;
  •  с конечной памятью;
  •  с бесконечной памятью.

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

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

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

По способу функционирования дискретные устройств делятся на

  •  детерминированные;
  •  вероятностные.

По способу формирования выходного сигнала. 

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

Дискретный автомат, для которого выходной сигнал зависит только от состояния и не зависит от входного сигнала, то есть  , называется автоматом Мура.

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

  •  автономные;
  •  неавтономные.

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

Доцент к. т. н., доцент                                                                      В.Трофименко

1 Математическая энциклопедия. Ред. коллегия: И. М. Виноградов (глав. ред.) [и др.] Т. 1 – М., "Советская энциклопедия", 1977